练习1 CF 1107E Vasya and Binary String
考虑区间DP, 只考虑从左侧消除的情况, 因为从右侧转移到左侧与从左侧转移到右侧是等价的
就是说设$dp[l][r][pre]$为$l$前有$pre$个与$l$同色的最大得分, 暴力转移就好了
ll dfs(int l, int r, int pre) {
if (l>r) return 0;
ll &ans = dp[l][r][pre];
if (ans) return ans;
if (l==r) return ans=a[pre];
ans = a[pre]+dfs(l+1,r,1);
REP(i,l+1,r) if (s[i]==s[l]) ans=max(ans,dfs(l+1,i-1,1)+dfs(i,r,pre+1));
return ans;
}
int main() {
scanf("%d%s", &n, s+1);
REP(i,1,n) scanf("%d", a+i);
printf("%lld\n", dfs(1,n,1));
}
练习2. CF 1107F Vasya and Endless Credits
考虑最优解的结构, 一定是有一部分全部还完, 还有一部分没有还完, 还完的直接在最开始买就行, 对于未还完的, 购买的时间一定连续, 并且$b_i$是非增的, 所以可以按照$b_i$排序转移即可, 复杂度$O(n^2)$
const int N = 1e3+10;
int n;
struct _ {
int a, b, k;
} a[N];
ll dp[N];
int main() {
scanf("%d", &n);
ll ans = 0;
REP(i,1,n) {
scanf("%d%d%d", &a[i].a, &a[i].b, &a[i].k);
}
sort(a+1,a+1+n,[](_ a,_ b){return a.b>b.b;});
REP(i,1,n) {
PER(j,0,n-1) {
dp[j+1]=max(dp[j+1],dp[j]+a[i].a-(ll)j*a[i].b);
dp[j]=max(dp[j],dp[j]+a[i].a-(ll)a[i].k*a[i].b);
}
}
printf("%lld\n", *max_element(dp,dp+1+n));
}
练习3
原文：https://www.cnblogs.com/uid001/p/10504202.html