IwfWcf's OI Log

ZOJ 2633 Full of Painting II 搜索减枝

2010-11-19T03:03:00.001+08:00

题目大意是一个线段分成n段涂色，有m种颜色可用，给出每种颜色的费用，每一段规定了所用的颜色以及涂色长度区间。同种颜色的涂色长度不能相同，求是否能按要求完成涂色以及最少需要花费的费用。

很典型的搜索题，主要用到了2个减枝技巧：

预处理出搜索到第i段时，第i+1段到第n段的涂色区间长度范围，如果剩余长度不在此范围内则可减枝。
预处理出搜索带第i段时，要用第i+1段到第n段规定的颜色完成剩余长度的涂色所需的最小费用。如果最小费用与当前费用之和大于或等于当前最优费用则可减枝。

其中第二个预处理通过O(nl^2)的DP完成。

2353428 2010-11-19 02:08:21 Accepted 2633 C++ 1320 212 IwfWcf

POJ 2227 The Wedding Juicer 二叉堆优先队列

2010-11-18T19:06:00.001+08:00

题目大意是在一个布满坑的地图上灌水，求最大储水量。

显然边界的坑是无法储水的，因此可以将边界的坑都加入一个保证坑的高度最小的优先队列（用二叉堆实现）。然后每次取出队列顶端的节点进行四个方向的灌水（如果高度比当前水位高度低则可增加储水量），将未曾加入队列的节点加入队列中继续这个过程直到队列为空即可。因为是从边界开始灌水，可以保证结果的正确性，同时显然可以确定每个坑只进出队列一次。故时间复杂度为O(nmlog(nm))。

7891534 IwfWcf 2227 Accepted 1288K 1719MS G++ 1631B 2010-11-18 18:22:05

HDU 3415 Max Sum of Max-K-sub-sequence 单调队列

2010-11-02T01:25:00.001+08:00

题目大意：给出一个有N个数字的环状序列，让你求一个长度不超过k的和最大的连续子序列。

环状的处理方法一般都是在序列的后面补多一段序列。用s[i]表示到第i位的序列和，对于终点位置为i的序列而言，其长度不超过k的和最大的连续子序列的起点位置就是满足min{s[j]}(j = i-k+1..i-1)的j。显然很容易构造数据卡朴素O(nk)的算法，求区间[i-k+1,i-1]内最小的s[j]就是RMQ问题，用二叉堆、Sparse Table、线段树之类的算法或数据结构可以做到在O(logk)的时间内完成查询，因此总的时间复杂度可以优化到O(nlogk)，对于这题的数据规模而言时限是可以接受的。

但通过单调队列可以将时间复杂度优化到O(n)。对于终点为i的序列，每次插入队列的是s[i-1]，显然队尾数值大于等于s[i-1]的元素是可以删除的，这样即可保证队列的单调性。而队首的要求则是位置大于等于i-k。这样对于每个终点为i的数列，队首即为最优起点。而每个位置的元素最多只会进出队列一次，因此可以保证时间复杂度是O(n)。

3144367 2010-11-02 00:19:10 Accepted 3415 609MS 1840K 944B C++ IwfWcf

POJ 2054 Color a Tree 巧妙的贪心思想

2010-10-27T13:00:00.001+08:00

题目大意就是要求 Sigma( i * Ci ) (i = 1 .. n) 的值最小，{ Ci } 是节点费用的一个排列，同时要满足父节点要出现在子节点前面。

考虑某一个可行解，就是{ Ci }的某一个排列。找到其中的最大值，比如为Ck，它有一个父节点比如Cp。显然Cp要出现在Ck之前。更进一步，Cp就应该出现在Ck的前一个位置。只有这样才有可能Sigma的值最小。不然我们可以将Ck位置向前移动，得到一个更小的Sigma值，并且不破坏上面的约束。既然Cp就出现在Ck的前一个位置，那么它们其实就是连在一起的，可以最为一个整体来看。因此可以把Ck和Cp合并为一个节点，这样就缩小为n-1的规模，缩小后的点的Ci值修改为他们的平均数，然后同样处理即可。这里的平均数，是指两个被合并的集合的Ci值之和除以两个集合的大小之和，譬如两个集合A，B，A的Ci和为Ca，大小为Ta，B的Ci和为Cb，大小为Tb，则合并后为(Ca+Cb)/(Ta+Tb)。

7795200    IwfWcf    2054    Accepted    752K    282MS    G++    1288B    2010-10-27 11:33:56

POJ 1521 Entropy 哈夫曼树

2010-10-26T23:36:00.001+08:00

题目大意是给出一个字符串，默认每个字符用8位二进制数（ASCII编码）表示，求以前缀不重复编码压缩后表示字符串所需的最少二进制数位数。

题目中介绍的按频率进行前缀不重复编码的压缩思路其实就是哈夫曼编码的思路，因此只需要构建出一颗哈夫曼树，然后计算原字符串节点的WPL（带权路径长度）即可。构建哈夫曼树的算法是：

首先把 n 个叶子结点看做 n 棵树（仅有一个结点的二叉树），把它们看做一个森林。
在森林中把权值最小和次小的两棵树合并成一棵树，该树根结点的权值是两棵子树权值之和。这时森林中还有 n-1 棵树。
重复第2步直到森林中只有一棵为止。此树就是哈夫曼树。

此外如果需要求具体的字符编码（即哈夫曼编码），则在树中令所有左分支取编码为 0 ，令所有右分支取编码为1。将从根结点起到某个叶子结点路径上的各左、右分支的编码顺序排列，就得这个叶子结点所代表的字符的二进制编码。

7794475 IwfWcf 1521 Accepted 756K 16MS G++ 1594B 2010-10-26 23:05:44

POJ 2492 A Bug's Life 并查集应用

2010-10-24T00:18:00.001+08:00

题目大意是给出m个虫子的交配组合，确定其中是否存在同性交配现象。

并查集的常规应用是判断两个元素是否处于同一个集合，但这题如果按照这种常规思路构建模型显然是行不通的。于是在常规的模型基础上增加一个数组sex[a]表示节点a与其根节点（注意和父节点相区分）的性别情况，true表示相同，false表示不同。

如果输入的a、b为同一集合中的元素，则直接比较其与根节点的性别情况即可判断是否为同性。如果处于不同集合，则合并两个集合后再进行比较。但合并之后要重新确定被合并的集合的原根节点与现根节点的性别情况。假设a的根节点为c，b的根节点为d，将d合并到c中，那么d相对于c的性别情况有以下可能：

sex[a] == true，sex[b] == true，即a、c的性别相同，b、d的性别相同，可知d，c的性别相反，即sex[d] = false；
sex[a] == true，sex[b] == false，即a、c的性别相同，b、d的性别不同，可知d，c的性别相同，即sex[d] = true；
sex[a] == false，sex[b] == true，和第二种情况相同，sex[d] = true；
sex[a] == false，sex[b] == false，即a、c的性别相反，c、d的性别相反，可知d，c的性别相反，即sex[d] = false；

即sex[d] = sex[a] ^ sex[b];

对sex的更新可以在求根节点的同时进行，根据与父节点的性别关系进行处理即可，利用递归实现非常便捷。此外在合并完成之后需要对被合并的集合内的节点的性别关系进行更新，之后再进行同性判断。

7781952 IwfWcf 2492 Accepted 404K 860MS G++ 1315B 2010-10-23 23:55:30

POJ 1129 Channel Allocation 平面着色问题

2010-10-20T18:35:00.001+08:00

题目大意是一个平面图中相邻（即在同一条边上）的两点不能用同一种颜色染色，求为给出的图染色所需的最少颜色。

先介绍一个定理--“将平面任意地细分为不相重迭的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。”，这个定理叫四色定理。基于这个定理，本题中所需的颜色数量不会超过4，因此只需用DFS判断能否用m种颜色完成染色，输出成功的m的最小值即可。

7756121 IwfWcf 1129 Accepted 388K 0MS G++ 1076B 2010-10-17 20:57:54

POJ 1050 To the Max 最大子矩阵和

2010-10-20T18:25:00.001+08:00

题目大意就是求一个矩阵中的最大子矩阵和。

求最大子矩阵和可以看作求最大子段和的二维平面版本，因此基本思路就是降维，将一行或一列进行压缩，然后再转化成求一维线段上的最大子段和。具体实现时可以用b[i,j]表示第j列从第1行到第i行的数字和，限定列压缩的起始行和结束行，用c[j]表示当前限制下到第j列为止的最大子矩阵和。记录下c[j]出现过的最大值即为最大子矩阵和。

7731901 IwfWcf 1050 Accepted 780K 47MS G++ 724B 2010-10-11 21:52:23

Vijos 1243 生产产品解题报告

2009-04-21T02:49:00.001+08:00

定义f[i,j]为生产前j个产品，最后一个在i机器上生产的最少耗费，容易推出朴素的状态转移方程。主要难点在于有同一台不能连续超过生产l个产品的规定，优化时间复杂度的关键在于降低在这l个状态中决策的时间复杂度。

定义g[i,j]为生产前j个产品，第j个在i机器上生产且第j-1个不在i机器上生产的最少耗费。易得f[i,j]=min(f[i,j],g[i,t]+sum[i,j]-sum[i,t])(j-l<t<=j);sum[i,j]表示在i机器生产前j个产品的费用和。可以发现影响决策的是g[i,t]-sum[i,t]的值，维护一个单调队列保存g[i,t]-sum[i,t](j-l<t<=j)的值，每次决策时取队首元素即可。

朴素的维护方法是利用堆来实现取最小的操作并在log(l)的时间内完成插入和删除操作。对于本题来说这一时间复杂度O(nnmlog(l))是可以接受的，但存在更优的方法使实际时间复杂度以及编程复杂度下降。显然当g[i,t]-sum[i,t]=g[i,p]-sum[i,p]时，若t>p，则保留p的状态就没有意义了。因此可以利用指针来维护一个单调队列，每次插入时二分寻找符合条件的插入点，并将队尾指针指向此。然后检查队首元素位置是否符合要求，如不符合则将队首指针后移，这样即可以实际时间复杂度远低于log(l)的代价完成队列的维护。对于本题的数据这一优化的效果非常明显。

R1216193 Accepted 100 From IwfWcf－ P1243 FPC Vivid Puppy 2009-4-21 2:26:30

Vijos 1144 小胖守皇宫解题报告

2009-04-11T01:17:00.003+08:00

非常经典的皇宫守护问题，用树形DP即可求解。对于每个点的覆盖可以分三种情况讨论：

在该点设守卫
在子节点设守卫
在父节点设守卫

分别用f[i,1],f[i,2],f[i,3]表示以上三种情况覆盖以该节点为根的子树所需的最少费用。则显然可以推出状态转移方程：

f[i,1]=∑min(f[j,1],f[j,2],f[j,3])+v[i](j为i的子节点);
f[i,2]=∑min(f[j,1],f[j,2])+mind(j为i的子节点;mind为所有子节点中f[j,1]-f[j,2]最小的，若存在f[j,1]<=f[j,2]则mind为0);对于叶节点，f[i,2]=v[i]。
f[i,3]=∑f[j,2](j为i的子节点);

程序实现时用一个队列维护当前待处理的已经处理完全部叶节点的节点，最后加入队列中的节点就是根节点。

R1206607 Accepted 100 From IwfWcf－ P1144 FPC Vag 6K 2009-4-11 1:01:21

Vijos 1021 Victoria的舞会1 解题报告

2009-03-28T22:09:00.001+08:00

这题实际上就是要求一个图中的最大点集，要求点集中的每个点的度不小于k。不过据说数据太弱，只需要将初始度小于k的点剔除即可，不需要对删边进行处理。

还是简单说一下我的做法吧，先将初始度小于k的点剔除，并且将与其连接的点的度减1，在此过程中如果有某个点的度被剪到小于k则加入队列并标记已经处理过。然后对队列中的点做同样处理，一直到没有点可以加入队列，扫一次所有点的度，统计不小于k的点的个数输出即可。由于每个点最多入队一次，所以时间复杂度是O(n^2)。

R1191343 Accepted 100 From IwfWcf－ P1021 FPC Vivid Puppy 2009-3-28 21:37:25

Vijos 1112 小胖的奇偶解题报告

2009-03-27T00:46:00.001+08:00

挺有意思的一题，题目给出的信息实际上可以得到一些进一步的信息，显然如果a-b有偶数个1则1-(a-1)与1-b的1的个数的奇偶性相同，而如果a-b有奇数个1则1-(a-1)与1-b的1的个数的奇偶性必定不同。

用same[i]表示与i奇偶性相同的集合，用dif[i]表示与i奇偶性不同的集合，则对于a-b有偶数个1的信息，合并same[a-1]与same[b]的集合以及合并dif[a-1]与dif[b]的集合。若合并后same[a-1]=dif[b]或same[b]=dif[a-1]则可判定该信息不可能被满足。类似的，对于a-b有奇数个1的信息，合并same[a-1]与dif[b]的集合以及合并same[b]与dif[a-1]的集合，若合并后same[a-1]=same[b]则可判定该信息不可能被满足。但我们可以发现，经过集合合并，以上判定信息可以用same[a-1]=dif[a-1]或same[b]=dif[b]中的任意一条表示。

由于本题的区间范围很大但询问数很小，需要用离散化或hash来对区间的起点和终点进行处理。

R1188765 Accepted 100 From IwfWcf－ P1112 FPC Vivid Puppy 2009-3-27 0:27:09

Vijos 1512 SuperBrother打鼹鼠解题报告

2009-03-25T21:47:00.001+08:00

二维树状数组，为了便于处理，将坐标全部做+1，sum[x1+1,y1+1,x2+1,y2+1]=sum[1,1,x2+1,y2+1]-sum[1,1,x1,y2+1]-sum[1,1,x2+1,y1]+sum[1,1,x1,y1];主要是注意做了转化后坐标处理的一些细节即可。

R1187587 Accepted 100 From IwfWcf－ P1512 FPC Vivid Puppy 2009-3-25 21:35:27

Vijos 1448 校门外的树解题报告

2009-03-23T23:59:00.003+08:00

本题有一种很形象的解法，在[l,r]上种树可以表示为在l处添加一个左括号，在r处添加一个右括号。求[l,r]之间种的树的种类数即[1,r]中左括号的数量-[1,l-1]中右括号的数量。而求和操作可以利用树状数组在O(logn)的时间复杂度内完成，所以总的时间复杂度是O(mlogn)。

注意在种树时要维护的数组变量的元素的下标在计算中有可能会超过word的范围，要用longint。之前没发现这一点，以为是Vijos对writeln处理的bug导致最后两个点超时多交了几次。

R1185426 Accepted 100 From IwfWcf－ P1448 FPC Vivid Puppy 2009-3-23 23:50:35

Vijos 1081 野生动物园解题报告

2009-03-22T21:38:00.001+08:00

注意题目中存在一个很重要的条件，区间是互不包含的，所以不需要用树套树，只需要对区间按左端点排序后，按顺序进行插入和删除操作即可维护平衡树使其只包含所求区间的元素。我使用SBT作为本题的数据结构，求第k小元素是其基本功能。由于插入和删除最多进行n次，所以时间复杂度是O(nlogn)。注意输出要按题目所给定的区间顺序输出，而且排序后的区间顺序。

这里说一下这题比较恶心的地方，仅仅按照提示使用write输出还是不够的，要每输出1000个答案就进行一次换行，否则最后4个点会"提示运行超时|格式错误"或"运行超时|无输出"……

R1184294 Accepted 100 From IwfWcf－ P1081 FPC Vivid Puppy 2009-3-22 21:21:13

Vijos 1507 郁闷的出纳员解题报告

2009-02-17T01:18:00.000+08:00

这是一道很经典的数据结构题，标准解法是平衡树，但也可以用线段树和树状数组来做。

树状数组解法：

用c[i]表示工资在[i-lowbit(i)+1,i]区间的人数，显然插入就是对每个包含k+d（用于维护新加入人员与原有人员之间的工资增减差额，是本题实现的一个非常巧妙的技巧）的区间元素+1，删除则是将包含c[min+d..min+d+k-1]所在区间的区间元素减去相应的人数。以下是删除部分的代码：

procedure delete(now,k:longint);
begin
while now<=maxn do
    begin
      dec(c[now],k); inc(now,lowbit(now));
    end;
end;

for j:=min+d to min+d+k-1 do
if c[j]>0 then
    begin
      inc(ans,c[j]); delete(j,c[j]);
    end;
inc(d,k);

关键在于如何求第k大工资，实际上我们是将其转化为求第total（现有员工数）-k+1小的工资。假设f[i]表示工资小于等于i的现有员工人数，则我们现在所需要求的实际上就是满足f[i]>=total-k+1的最小的i值。因此很容易想到一个每次查询复杂度为O(log n*log n)的算法，即二分工资并利用树状数组求出工资小于等于当前工资的人数。但这种算法还是没能完全利用树状数组的储存特性，假设所求的最小的i值为ans'，则改进算法的核心思想实际上就是将ans'分割成一段段长度为2的倍数的区间累加逼近。由于不太好说明，请结合代码进行理解：

function getkth(k:longint):longint;
var now,p,s:longint;
begin
if total-ans<k then exit(-1);
k:=total-ans-k+1; now:=0; p:=0; s:=1 shl 18;
while (now<k) and (s>0) do
    begin
      while (c[p+s]+now>=k) and (s>0) do s:=s shr 1;
      if s=0 then break;
      inc(p,s); inc(now,c[p]);
    end;
exit(p+1-d);
end;

另外由于Vijos对于大数据的处理存在缺陷，本题的输出不能换行，否则会导致TLE（我多交了3次后的忠告）......

R1147973 Accepted 100 From IwfWcf－ P1507 FPC Vivid Puppy 2009-2-17 1:15:05

平衡树解法：

我是用SBT退化版来写的，整个程序只有82行。做法同样是利用一个变量d来维护新加入人员与原有人员之间的工资增减差额关系，新增员工即插入一个节点，统计每次扣工资后员工离开的数量即删除工资最接近min+d的子树后统计根节点的size域的减少量。代码如下：

procedure delete(var t:longint;v:longint);
begin
if t=0 then exit;
if key[t]<v then
    begin
      t:=r[t]; delete(t,v);
    end
    else delete(l[t],v);
if t>0 then s[t]:=s[l[t]]+s[r[t]]+1;
end;

inc(d,k); ltotal:=s[root];
delete(root,min+d); inc(ans,ltotal-s[root]);

求第k大的工资实际上即转化为求第total(当前员工总数)-k+1小的工资是多少，这是SBT本身即支持的操作。

Vijos 1002 过河解题报告

2009-02-15T16:48:00.001+08:00

这题的基本思路就是背包，但长度太长，如果不加优化的朴素DP无论时间复杂度还是空间复杂度都无法承受。但很容易发现石头总共只有100个，如果能把无石子路段进行压缩则可以使复杂度符合要求。经过证明可以发现只要将长度大于100的无石子路段压到100就可以保证得到的解是正确的。

R1146659 Accepted 100 From IwfWcf－ P1002 FPC Vijos Dolphin 2009-2-15 16:24:47

Vijos 1432 数学家之梦解题报告

2009-02-14T22:02:00.001+08:00

n柱Hanoi Tower问题，由于nm都很大，所以不可能用DP来解决，只能通过n柱Hanoi Tower的有规律数列来计算。该数列是由2^0-2^(m-1)组成，第i个数字有1+(i-1)*(n-3)个。数列之和就是在n柱汉诺塔上移动m个盘子所需要的最少次数。

R1145939 Accepted 100 From IwfWcf－ P1432 FPC Vivid Puppy 2009-2-14 21:59:59

Vijos 1426 兴奋剂检查解题报告

2009-02-14T20:55:00.001+08:00

这道题本质就是n维背包，但由于每个背包的容量不确定，因此不能使用朴素的状态储存方式，必须对状态进行压缩。题目给了一个提示V1*V2*V3*...*Vm<=5000000，这实际上可以理解为如果将各个背包限制容量先以二进制的方式表示，再将各个背包顺次连接成一个“大背包”，所需要的二进制数转化为十进制不超过5000000。状态转移时需要应用一些位运算的处理操作，个人感觉这道题比较具有代表性，因此把状态转移部分的代码贴出来：

for i:=1 to n do
    for j:=s-v[i] downto 0 do
      begin
        if f[j]+a[i]<=f[j+v[i]] then continue;
        success:=true;
        for k:=1 to m do
          if b[i,k]+(j-(j shr l[k] shl l[k])) shr l[k-1]>c[k] then
            begin
              success:=false; break;
            end;
        if success then f[j+v[i]]:=f[j]+a[i];
      end;

其中s表示的是m个背包都是最大数值时的状态，v[i]表示第i个物品所需的背包空间的状态，b[i,k]表示的是第i个物品所需的第k个背包的容量，l[k]表示前k个背包的状态包含的二进制位数，f[i]表示i状态时背包所能获得的最大价值。

R1145830 Accepted 100 From IwfWcf－ P1426 FPC Vivid Puppy 2009-2-14 20:49:55

Vijos 1421 更换轮胎解题报告

2009-02-13T13:15:00.001+08:00

用f[i,j]表示第i圈用第j种轮胎完成所需要的最少时间，用minl表示完成上一圈所需的最少时间，则易得状态转移方程：f[i,j]:=min(f[i-1,j],minl+c)+t[i,j];

如果一边读入一边DP并且使用滚动数组优化可以将空间复杂度降到O(n)。

R1144131 Accepted 100 From IwfWcf－ P1421 FPC Vivid Puppy 2009-2-13 13:13:51

Vijos 1417 魔法塔防解题报告

2009-02-12T14:03:00.024+08:00

首先，容易证明，红法师一定排在最后。（提示：只需证明，将RG或RB交换成GR或BR一定更优。）所以，若使用r个红法师，只须确定其余N-r个排在前面的蓝、绿法师如何摆放，这一步可以使用DP来解决。

设f[g][b]表示使用g个绿法师、b个蓝法师可造成的最大伤害，求解f[g][b]只须枚举最后一格放的是何种法师，可以由f[g-1][b]和f[g][b-1]递推得到。

初始化：
f[0, 0]:=0; {没有法师}
f[0, 1]:=0; {只放一个绿法师}
f[0, j]:=f[0, j-1]+(j-1)*g*t;(1<=j<=n) {不放蓝法师，在前j个位置放绿法师的(最大)伤害}
f[i, 0]:=0;(1<=i<=n) {不放绿法师，在前i个位置放置蓝法师，伤害均为零}

状态转移方程:
f[i, j]:=max(f[i-1, j] + j*g*(t+(i-1)*b){第i+j个位置放蓝法师},f[i, j-1] + (j-1)*g*(t+i*b){第i+j个位置放绿法师});

由于f[i,j]只与f[i-1,j]和f[i,j-1]有关，所以可以利用滚动数组将空间复杂度降到O(n)。

对于每个f[g][b]，加上最后的N-g-b个红法师带来的伤害，以及在红法师的区域由于中毒带来的伤害（后者易忽视），找到最优值即可。算法的复杂度是O(N^2)。

由于结果较大，需要使用64位整数（注意中间变量运算也会溢出longint范围），另外提醒一下最后一个数据是很恶心的65536，不能用word存......

R1143341 Accepted 100 From IwfWcf－ P1417 FPC Vivid Puppy 2009-2-12 14:00:16

Vijos 1395 HYH的逻辑电路解题报告

2009-02-11T13:39:00.009+08:00

采用f[node,boolean]来描述一个状态，表示节点node输出boolean时，需要改变的最少节点数。状态转移按照节点node的运算符，枚举两个儿子节点的输出，分为And、Or和Xor三种情况进行转移：

And的情况：
f[i,0]:=min(f[lson,0]+f[rson,0],min(f[lson,1]+f[rson,0],f[lson,0]+f[rson,1]));
f[i,1]:=f[lson,1]+f[rson,1];

Or的情况：
f[i,0]:=f[lson,0]+f[rson,0];
f[i,1]:=min(f[lson,1]+f[rson,1],min(f[lson,1]+f[rson,0],f[lson,0]+f[rson,1]));

Xor的情况：
f[i,0]:=min(f[lson,0]+f[rson,0],f[lson,1]+f[rson,1]);
f[i,1]:=min(f[lson,1]+f[rson,0],f[lson,0]+f[rson,1]);

从根元件开始递归求解即可，最后输出的是根元件两种状态的较大者。

R1142172 Accepted 100 From IwfWcf－ P1395 FPC Vivid Puppy 2009-2-11 13:36:30

Vijos 1386 矿工配餐解题报告

2009-02-10T16:49:00.021+08:00

由于食物的分配顺序是确定的，所以可以以前面i个食物作为阶段划分。而只有每个煤矿的最后两个食物的类型会对后面造成影响，因此可以用状态f[i,j,k,l,m]表示分配到第i个食物时，第一个煤矿最后两个食物依次是j和k，第二个煤矿最后两个食物依次是l和m时的总最大产量。

状态转移方程：

放在第一个煤矿：f[i+1,k,food[i+1],l,m]:=max(f[i+1,k,food[i+1],l,m],f[i,j,k,l,m]+dif(j,k,food[i+1]));

放在第二个煤矿：f[i+1,j,k,m,food[i+1]]:=max(f[i+1,j,k,m,food[i+1]],f[i,j,k,l,m]+dif(l,m,food[i+1]));

由于f[i+1]只与f[i]有关，所以可以用滚动数组将空间复杂度降到O(2*4^4)。

R1141347 Accepted 100 From IwfWcf－ P1386 FPC Vivid Puppy 2009-2-10 16:47:16

Vijos 1355 车队过桥问题解题报告

2009-02-06T02:24:00.001+08:00

用f[i]表示前i辆车过桥所需的最短时间（单位：小时），易得状态转移方程f[i]=min(f[i],f[j]+len/minv)(1<=i<=n,0<=j<i,w[j+1]+…+w[i]<=max)，minv即min(v[j+1]..v[i])。

R1135966 Accepted 100 From IwfWcf－ P1355 FPC Vijos Dolphin 2009-2-6 2:16:52

Vijos 1351 棋盘制作解题报告

2009-02-05T10:12:00.001+08:00

由于第一问所求的正方形必定包含在所有极大子矩形中，因此利用极大化思想可以在O(nm)的时间复杂度内求出最大子矩形，在枚举所有极大子矩形的过程中记录下最大的较短边长度，其平方即是第一问的答案。

简单地说一下在O(nm)的时间复杂度内枚举所有极大子矩形的算法，枚举棋盘上的每个棋子，先求出其向上、向左和向右最大可拓展到的位置，分别用h[i,j]、l[i,j]和r[i,j]记录。然后再枚举一次全部棋子，若h[i,j]>1则l[i,j]=max(l[i,j],l[i-1,j]),r[i,j]=min(r[i,j],r[i-1,j])。这样既可得到每个棋子在其向上拓展最高的前提下的极大子矩形，这样就包含了所有的极大子矩形。

R1134170 Accepted 100 From IwfWcf－ P1351 FPC Vijos Dolphin 2009-2-5 9:54:59

IwfWcf's OI Log

ZOJ 2633 Full of Painting II 搜索减枝

POJ 2227 The Wedding Juicer 二叉堆优先队列

HDU 3415 Max Sum of Max-K-sub-sequence 单调队列

POJ 2054 Color a Tree 巧妙的贪心思想

POJ 1521 Entropy 哈夫曼树

POJ 2492 A Bug's Life 并查集应用

POJ 1129 Channel Allocation 平面着色问题

POJ 1050 To the Max 最大子矩阵和

Vijos 1243 生产产品 解题报告

Vijos 1144 小胖守皇宫 解题报告

Vijos 1021 Victoria的舞会1 解题报告

Vijos 1112 小胖的奇偶 解题报告

Vijos 1512 SuperBrother打鼹鼠 解题报告

Vijos 1448 校门外的树 解题报告

Vijos 1081 野生动物园 解题报告

Vijos 1507 郁闷的出纳员 解题报告

Vijos 1002 过河 解题报告

Vijos 1432 数学家之梦 解题报告

Vijos 1426 兴奋剂检查 解题报告

Vijos 1421 更换轮胎 解题报告

Vijos 1417 魔法塔防 解题报告

Vijos 1395 HYH的逻辑电路 解题报告

Vijos 1386 矿工配餐 解题报告

Vijos 1355 车队过桥问题 解题报告

Vijos 1351 棋盘制作 解题报告