Loj 507 接竹竿 题解
Loj链接:接竹竿
$ {scr color {SkyBlue}{ ext{Solution}}} $
题目大意:
给定一个数组,每次加入一种颜色的数,可以取走与它颜色相同的两个数之间的所有数,问最后取走的所有数中最大和是多少
分析:
第一眼看到的是二分答案,但不知道二分的check()函数怎么写。
没办法,考虑DP(其实是因为我贪心写挂了)
DP如果可以,那么要至少要满足一下几个条件:
- DP前面的选择情况不影响后面的选择情况(前不影响后)
- DP可以转移
时间、空间复杂度等可以以后慢慢优化啦!
尝试一下?
尝试列出转移方程:
$$dp[i]=max egin{cases} dp[i-1]& ext{$c_i$}!={c_j}\ dp[j-1] + sum_{k=1}^{i} v_k – sum_{k=1}^{j-1} v_k & ext{$c_i==c_j$} end{cases}$$
这样我们就列出了一个$O(n^3)$的DP转移方程。
接下来就考虑优化呗!
优化
- 前缀和优化
易发现,DP方程里有很多类似求$sum_{i}^{j} v_k$的,并且每次DP推方程时都要重新计算一遍
其实,求连续一段值的和,我们可以用前缀和优化啊!
现在方程就是$O(n^2)$的了。
示例代码(会TLE!):
for(int i=1;i<=n;i++) scanf("%lld",&a[i].y),a[i].y+=a[i-1].y; for(int i=1;i<=n;i++) { dp[i]=dp[i-1]; for(int j=1;j<i;j++) if(a[i].x==a[j].x) dp[i]=max(dp[i],dp[j-1]+a[i].y-a[j-1].y);
}