首页 > 代码库 > 佳佳的魔杖 (vijos 1283)

佳佳的魔杖 (vijos 1283)

题目大意:

一根树枝有N段,每一段有一个分数,可以选取一些不完全包含(可以相交)的区间,每次选取可以得到区间里所有数之和的分数。 求最大得分。

 

解题过程:

1.很明显的dp,默认选取区间的顺序是从左往右,F[i][j] 表示最后选的区间为[i,j]的最优解(i<=j)。 显然 F[i][j]=max{F[p][q]}+sum[i][j]. (p<i && q<j);

但是复杂度显然太高,达到了O(N^4)。。 此题的方程很容易想到,难得也正是 如何 降低复杂度。

2.考虑到方程中q<j的条件是很好满足的,以j为阶段,那么只要取阶段j-1的值 就可以满足q<j了。  那么我们用一个辅助数组g[i][j]表示max{F[p][q]}(p<=i && q<=j),维护g[i][j]只要每次做完阶段j,for i=1->j  g[i][j]=max{g[i-1][j],F[i][j],g[i][j-1]};

这样状态转移方程就变成了F[i][j]=g[i-1][j-1]+sum[i][j] . 复杂度成功降到了O(N^2);

 

总结:部分DP题一般最简单的状态转移方程很容易得到,但是复杂度往往太高,需要维护一个辅助数组来降低复杂度。

佳佳的魔杖 (vijos 1283)