题目大意是一个线段分成n段涂色，有m种颜色可用，给出每种颜色的费用，每一段规定了所用的颜色以及涂色长度区间。同种颜色的涂色长度不能相同，求是否能按要求完成涂色以及最少需要花费的费用。
很典型的搜索题，主要用到了2个减枝技巧：
其中第二个预处理通过O(nl^2)的DP完成。
2353428 2010-11-19 02:08:21 Accepted 2633 C++ 1320 212 IwfWcf
题目大意就是求一个矩阵中的最大子矩阵和。
求最大子矩阵和可以看作求最大子段和的二维平面版本，因此基本思路就是降维，将一行或一列进行压缩，然后再转化成求一维线段上的最大子段和。具体实现时可以用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
定义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
非常经典的皇宫守护问题，用树形DP即可求解。对于每个点的覆盖可以分三种情况讨论：
分别用f[i,1],f[i,2],f[i,3]表示以上三种情况覆盖以该节点为根的子树所需的最少费用。则显然可以推出状态转移方程：
程序实现时用一个队列维护当前待处理的已经处理完全部叶节点的节点，最后加入队列中的节点就是根节点。
R1206607 Accepted 100 From IwfWcf－ P1144 FPC Vag 6K 2009-4-11 1:01:21
这题的基本思路就是背包，但长度太长，如果不加优化的朴素DP无论时间复杂度还是空间复杂度都无法承受。但很容易发现石头总共只有100个，如果能把无石子路段进行压缩则可以使复杂度符合要求。经过证明可以发现只要将长度大于100的无石子路段压到100就可以保证得到的解是正确的。
R1146659 Accepted 100 From IwfWcf－ P1002 FPC Vijos Dolphin 2009-2-15 16:24:47
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
这道题本质就是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
用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
首先，容易证明，红法师一定排在最后。（提示：只需证明，将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
采用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
由于食物的分配顺序是确定的，所以可以以前面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
用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
由于第一问所求的正方形必定包含在所有极大子矩形中，因此利用极大化思想可以在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
典型的二维背包，用f[i,j,k]表示从前i种食物中挑选，总体积不超过j，总重量不超过k所能获得的最大卡路里之和。则f[i,j,k]=max(f[i,j,k],f[i-1,j-v[i],k-w[i]]+cal[i])(1<=i<=n,v[i]<=j<=vmax,w[i]<=k<=wmax);由于f[i]只与f[i-1]有关，所以可以用滚动数组将空间复杂度优化到O(vw)。
R1128843 Accepted 100 From IwfWcf－ P1334 FPC Vijos Dolphin 2009-2-2 1:29:08
推出状态转移方程不难，用f[i]表示到第i个人为止最少需要多少辆车，则f[i]=min(f[i],f[j]+1)(0<=j<=i-1)。关键在于如何快速判断能否从一个状态转移到下一个状态，也即快捷地表示出题目中的限制条件。这里介绍一个很巧妙的方法，用g[i]表示到第i个人为止h与j的人数差，显然当abs(g[i]-g[j])=i-j时即从第j+1个人到第i个人中间没有另一球队的球迷。而abs(g[i]-g[j])<=d时即从第j+1个人到第i个人中间，不同球队的球迷的相差人数不大于d。
另外需要注意的是第j+1个人到第i个人不能坐同一辆车不代表第j个人到第i个人不能做同一辆车。
R1128841 Accepted 100 From IwfWcf－ P1331 FPC Vijos Dolphin 2009-2-2 1:05:11
很Orz的一题，由于没想到什么好的优化，只好写了个O(n^2)的DP交上去，同一个程序交了3次才AC……
看了一下题解，没看到什么更好的方法，所以还是写写我的RP算法吧……用f[i,j]表示从第i位起j个字母的子串要成为回文词最少需要添加的字符数，于是可得到一个和LCS有点像的状态转移方程，f[i,j]=f[i+1,j-2](s[i]=s[i+j-1]),min(f[i,j-1],f[i+1,j-1])+1(s[i]<>s[i+j-1])。由于f[i]只与f[i+1]有关，所以可以利用滚动数组将空间复杂度降到O(n)。
R1126951 Accepted 100 From IwfWcf－ P1327 FPC Vijos Dolphin 2009-1-31 16:02:32
一开始想当然地认为是贪心，于是贡献了一次WA。给出一个贪心的反例数据：
50 5
40 10
10 40
10 5
10 3
10 2
答案应该是4，而贪心由于会把前两道题安排在同一个月解决，会造成要多工作一个月来支付后3题。
用f[i,j]表示最后一个月解决的题目是i到j，则状态转移方程f[i,j]=min(f[i,j],f[k,i-1]+1)(sum_a[j]-sum_a[i-1]+sum_b[i-1]-sum_b[k-1]<=m),min(f[i,j],f[k,i-1]+2)(sum_a[j]-sum_a[i-1]+sum_b[i-1]-sum_b[k-1]>m)
当然，状态转移的前提条件还有其本身是一个有效状态（即月结不能超过m）。
R1126414 Accepted 100 From IwfWcf－ P1322 FPC Vijos Dolphin 2009-1-30 21:17:34
用f[i]表示以i结尾的最长序列长度，可以证明在序列长度相等的情况下，最后一个数的长度越小则第一个数的长度越大（即倒序枚举j）。用g[i]记录当f[i]取得最大值时以第i位结尾的数字字串。由此可得状态转移方程：f[i]=max(f[i],f[j]+1)(1<=i<=length(s),1<=j<=i,g[i]>g[j])。递归求解（用g[length(s)]的长度可以推出前一个状态）输出答案即可。
R1124895 Accepted 100 From IwfWcf－ P1306 FPC Vijos Dolphin 2009-1-28 21:06:20
用f[i,j]表示最后一节魔杖的起始点不超过i，结束点不超过j可获得的最大魔力值之和。f[i,j]最多只能从三种状态转移得到，则可以推出以下状态转移方程：
f[i,j]= Max{ f[i-1,j] ,f[i,j-1] 当i<=j-1时 ,f[i-1,j-1] + M[j]+M[j+1]+...+M[i] 当lo<=L[j]+L[j+1]+...L[i]<=hi时 }
由于m[i]可被多次计算，故f[i,j]的最大值有可能超过longint。
R1124218 Accepted 100 From IwfWcf－ P1283 FPC Vijos Dolphin 2009-1-27 16:36:27
囧……这题再次让我对我的题目理解能力无语……并且在为了理解题意看题解的过程中不小心看到了某些同学的善意提醒，于是在不知道数据已经修正的情况下白白贡献了一次WA……
理解了题意后DP就很容易想到了，首先先解释一下不可能得到的礼物是指以下两种情况：1、v不能被h整除（也就是不能在整秒末落在格子上）；2、从一开始就从最初的位置向该位置移动也无法接到。
于是在预处理时就可以求出第二问的答案，同时用c[i,j]记录下第i秒在第j个格可以获得礼物价值总和，用tmax记录下可得到的礼物的最大的落下时间。则可以得到DP的状态转移方程：f[i,j]=max(f[i-1,j-1],f[i-1,j],f[i-1,j+1])+c[i,j](1<=i<=tmax,1<=j<=w)。由于f[i]只与f[i-1]有关，因此可以用滚动数组优化，但由于c数组无法使用这一优化，因此空间复杂度并没有降低，只是常数低了罢了。
R1123984 Accepted 100 From IwfWcf－ P1235 FPC Vijos Dolphin 2009-1-26 21:37:56
博文
所有评论
