首页 > 代码库 > 佳佳的魔杖 (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)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。