本文最后更新于 2024年9月7日 下午
AT_DP_C Vacation
洛谷 Link
DP 板子题。设 fi,j 表示截止到第 i 天时做第 j 件事的幸福值总和。
则易得转移方程为:
fi,1=max(fi−1,2,fi−1,3)fi,2=max(fi−1,1,fi−1,3)fi,3=max(fi−1,1,fi−1,2)
Core Code:
1 2 3 4 5 6
| for(int i=1;i<=n;i++) { f[i][1]=max(f[i-1][2],f[i-1][3])+a[i]; f[i][2]=max(f[i-1][1],f[i-1][3])+b[i]; f[i][3]=max(f[i-1][1],f[i-1][2])+c[i]; }
|
AT_DP_K Stones
洛谷 Link
显然当一名玩家操作完成后石子数量为 0,则这名玩家必胜。
设 fi 表示剩余 i 枚石子当前操作的人的输赢情况 (1/0),可以发现当且仅当当前操作的上一步操作必输,当前操作才可以必胜,即如果有 aj 使得 fi−aj=0,则 fi=1。
初始化 f0=0,则有:
fi={1,0,aj≤i,fi−aj=0otherwise.
Core Code:
1 2 3 4 5 6 7 8
| f[0]=0; for(int i=1;i<=k;i++) { for(int j=1;j<=n;j++) { if(i-a[j]>=0 && !f[i-a[j]]) f[i]=1; } }
|
TDPC_IWI イウィ
洛谷 Link
区间 DP,类似合并石子。
我们定义 fi,j 记录 i 到 j 能删掉多少字符,显然最后答案应除以 3。
因为答案计算的是最大的步数,那么对于一个大区间,在一般情况下的答案就应该是其分成的两个小区间的答案之和。考虑枚举这两个区间之间的分界点 k ,答案取最大值即可。
本题还需要特判一种特殊情况。如果 si 和 sj 为 i
,sk 为 w
,且中间的两个小段可以被完全删除。那么,当中间的被删掉之后,左右的 i
和中间的 w
就会拼在一起,也可以删掉,那么这个区间的答案就应该是它的长度,但显然直接相加有可能会出错。
Core Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| for(int a=2;a<=len;a++) { for(int i=1;a+i-1<=len;i++) { int j=a+i-1; for(int k=i;k<j;k++) { f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]); if(s[i]=='i' && s[j]=='i' && s[k]=='w' && f[i+1][k-1] == k-i-1 && f[k+1][j-1] == j-1-k) { f[i][j]=j-i+1; } } } } write(f[1][len]/3);
|
ABC247F Cards
AT_DP_D Knapsack 1
ABC286D Money in Hand