AtCoder DP 系列刷题记录

AT_DP_C Vacation

洛谷 Link

DP 板子题。设 $f_{i,j}$ 表示截止到第 $i$ 天时做第 $j$ 件事的幸福值总和。

则易得转移方程为：

$$f_{i,1}=\max(f_{i-1,2},f_{i-1,3})\\ f_{i,2}=\max(f_{i-1,1},f_{i-1,3})\\ f_{i,3}=\max(f_{i-1,1},f_{i-1,2})$$

Core Code:

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$，则这名玩家必胜。

设 $f_i$ 表示剩余 $i$ 枚石子当前操作的人的输赢情况 ($1/0$)，可以发现当且仅当当前操作的上一步操作必输，当前操作才可以必胜，即如果有 $a_j$ 使得 $f_{i-a_j}=0$，则 $f_i=1$。

初始化 $f_0=0$，则有：

$$f_i=\begin{cases} 1,&a_j\leq i,f_{i-a_j}=0\\ 0 ,& \text{otherwise.} \end{cases}$$

Core Code:

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，类似合并石子。

我们定义 $f_{i,j}$ 记录 $i$ 到 $j$ 能删掉多少字符，显然最后答案应除以 $3$。

因为答案计算的是最大的步数，那么对于一个大区间，在一般情况下的答案就应该是其分成的两个小区间的答案之和。考虑枚举这两个区间之间的分界点 $k$ ，答案取最大值即可。

本题还需要特判一种特殊情况。如果 $s_i$ 和 $s_j$ 为 i，$s_k$ 为 w，且中间的两个小段可以被完全删除。那么，当中间的被删掉之后，左右的 i 和中间的 w 就会拼在一起，也可以删掉，那么这个区间的答案就应该是它的长度，但显然直接相加有可能会出错。

Core Code:

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