Vijos 1417 魔法塔防 解题报告

首先，容易证明，红法师一定排在最后。（提示：只需证明，将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