Vijos 1283 佳佳的魔杖 解题报告

用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