偶然发现了 Atcoder 的一场动态规划专项赛，视若珍宝。

欢迎大家去洛谷练习，因为有翻译，有题解，当然也推荐 Vjudge。

A.Frog 1

$f_i$ 表示跳到 $i$ 需要的费用。

这道题显然有两种选项，直接按顺序 DP 即可。

f_i=\min(f_{i-1}+|h_i-h_{i-1}|,f_{i-2}+|h_i-h_{i-2}|)

#include<bits/stdc++.h>
using namespace std;
long long n,h[100005],f[100005];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>h[i];
    }
    memset(f,127,sizeof(f));
    f[1]=0;
    for(int i=2;i<=n;i++)
    {
        f[i]=min(f[i-1]+abs(h[i]-h[i-1]),f[i-2]+abs(h[i]-h[i-2]));
    }
    cout<<f[n]<<endl;
    return 0;
}

B.Frog 2

$f_i$ 表示跳到 $i$ 需要的费用。

这道题一次可以跳 $k$ 格了，但是也是纸老虎，再加一层循环即可。

f_i=\min_{j=\min(i-k,1)}^{i-1}(f_{j}+|h_i-h_{j}|);

#include<bits/stdc++.h>
using namespace std;
long long n,k,h[100005],f[100005];
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>h[i];
    }
    memset(f,127,sizeof(f));
    f[1]=0;
    for(int i=2;i<=n;i++)
    {
        for(int j=i-1;j>=1&&j+k>=i;j--)
        {
            f[i]=min(f[i],f[j]+abs(h[i]-h[j]));
        }   
    }
    cout<<f[n]<<endl;
    return 0;
}

C.Vacation

$f_{i,j}$ 表示第 $i$ 天做活动 $j$ 的最大幸福值。

对于每个状态，显然有两种选项，直接按顺序 DP 即可。

f_{i,j}=\max(f_{i-1,(j+1)\bmod 3},f_{i-1,(j+2)\bmod3})+a_{i,j}

那啥，公式里的一些东西和题目描述的不太一样，相信大家可以看懂。

#include<bits/stdc++.h>
using namespace std;
long long n,a[100005][3],f[100005][3];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i][0]>>a[i][1]>>a[i][2];
    for(int i=1;i<=n;i++)
        for(int j=0;j<=2;j++)
            f[i][j]=max(f[i-1][(j+1)%3],f[i-1][(j+2)%3])+a[i][j];
    cout<<max(f[n][0],max(f[n][1],f[n][2]))<<endl;
    return 0;
}

D.Knapsack 1

一眼背包，还是01背包的板子。

$f_{i,j}$ 为价值为选前 $i$ 个物品，重量为 $j$ 时，价值最大是多少。

f_{i,j}=\max(f_{i-1,j-w_i}+v_i,f_{i-1,j})

答案是从大到小找到的第一个 $i$ 使得 $f_i<W$ 。

显然可以压缩成一维，不过要倒着来，避免已经计算的部分影响当前计算。

#include<bits/stdc++.h>
using namespace std;
long long n,t,w,v,f[100005];
int main(){
    cin>>t>>n;
    for(int i=1;i<=t;i++)
    {
        cin>>w>>v;
        for(int j=n;j>=w;j--)
            f[j]=max(f[j],f[j-w]+v);        
    }
    cout<<f[n];
}

E.Knapsack 2

一眼背包，还是01背包的板子，不过略有变化。

受数据影响，我们需要变形。

$f_{i,j}$ 为价值为选前 $i$ 个物品，价值为 $j$ 时，重量最小是多少。

f_{i,j}=\min(f_{i-1,j-v_i}+w_i,f_{i-1,j})

答案是从大到小找到的第一个 $i$ 使得 $f_i<W$ 。

显然可以压缩成一维，不过要倒着来，避免已经计算的部分影响当前计算。

#include<bits/stdc++.h>
using namespace std;
long long n,t,w,v,f[100005];
int main(){
    cin>>t>>n;
    memset(f,127,sizeof(f));
	f[0]=0; 
    for(int i=1;i<=t;i++)
    {
        cin>>w>>v;
        for(int j=100000;j>=v;j--)
            f[j]=min(f[j],f[j-v]+w);        
    }
	for(int j=100000;j>=0;j--)
	{
		if(f[j]<=n)
		{
			cout<<j<<endl;
			return 0;
		}
	} 
}

F.LCS

这道题显然就是最长公共子序列的板题。

$f_{i,j}$ 表示字符串1 的前 $i$ 个字符与字符串2 的前 $j$ 个字符的最长公共子序列的长度。

f_{i,j}= \begin{cases} f_{i-1,j-1}+1(a_i=b_j)\\ \max(f_{i-1,j},f_{i,j-1})(a_i \not= b_j) \end{cases}

不过需要记录路径，还是很简单的。

我们记录每个状态有哪个状态转移而来，然后倒推答案。

#include <bits/stdc++.h>
using namespace std;
long long f[3005][3005],s[3005][3005][2],n,m;
char a[3005],b[3005];
void dg(long long x,long long y)
{
	if(x==0&&y==0)return;
	dg(s[x][y][0],s[x][y][1]);
	if(s[x][y][0]==x-1&&s[x][y][1]==y-1)
	{
		cout<<a[x];
	}
}
int main() {
	cin>>(a+1)>>(b+1);
	n=strlen(a+1);
	m=strlen(b+1); 
    for(int i=1;i<=n;i++)
	{
        for(int j=1;j<=m;j++)
		{
            if(a[i]==b[j])
			{
                f[i][j]=f[i-1][j-1]+1;
                s[i][j][0]=i-1,s[i][j][1]=j-1;
            } 
			else 
			{
                if(f[i][j-1]>f[i-1][j])
				{
                    f[i][j]=f[i][j-1];
                    s[i][j][0]=i,s[i][j][1]=j-1;
                }
				else 
				{
                    f[i][j]=f[i-1][j];
                    s[i][j][0]=i-1,s[i][j][1]=j;
                }
            }
        }
    }
    dg(n,m);
}

G.Longest Path

$f_i$ 表示从点 $i$ 开始走，能走的最远距离。

f_i=\max(0,\max_{(i,j)\in E}(f_j+1))

那正常来说，我们要找出度为零的点，然后倒退求解，整体使用拓扑排序，有些小麻烦。

如果用记忆化搜索，就方便多了。

#include<bits/stdc++.h>
using namespace std;
long long n,m,x,y,f[100005],ans;
vector<long long>v[100005];
long long dfs(long long x)
{
	if(f[x]==0)
	{
		for(auto i:v[x])
		{
			f[x]=max(dfs(i)+1,f[x]);
		}
	}
	return f[x];
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y;
		v[x].push_back(y);
	}
	for(int i=1;i<=n;i++)
	{
		ans=max(dfs(i),ans);
	}
	cout<<ans<<endl; 
}

H.Grid 1

这题像休息的驿站，反而简单一点，赶紧做了去看下一题吧！

$f_{i,j}$ 表示从 $(1,1)$ 走到 $(i,j)$ 的方案数。

f_{i,j}= \begin{cases} 0(c_{i,j}=\#)\\ f_{i-1,j}+f_{i,j-1}(c_{i,j}=.) \end{cases}

#include<bits/stdc++.h>
using namespace std;
long long n,m,f[1005][1005];
char c[1005][1005];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>c[i][j];
		} 
	}
	f[1][1]=1; 
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(c[i][j]=='#')continue;
			if(i==j&&i==1)continue;
			f[i][j]=f[i-1][j]+f[i][j-1];
			f[i][j]%= 1000000007;
		}
	} 
	cout<<f[n][m]<<endl; 
}

I.Coin

这是一道概率动态规划，但是比较简单，跟一些比较复杂的期望动态规划比真的太简单了。

$f_{i,j}$ 表示前 $i$ 个硬币正面 $j$ 次的概率。

f_{i,j}=f_{i-1,j-1}\times a_i+f_{i-1,j}\times (1-a_i)

最后将 $f_{n,i}(\frac{n}{2}+1\leq i\leq n)$ 累加即可。

#include<bits/stdc++.h>
using namespace std;
long long n;
double a[10005],f[3000][3000],ans;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	f[0][0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=i;j++)
		{
			f[i][j]=f[i-1][j-1]*a[i]+f[i-1][j]*(1-a[i]);
		}
	}
	for(int i=(n+1)/2;i<=n;++i){
		ans+=f[n][i];
	}
	printf("%.11lf",ans);
	return 0;
}

J.Sushi

一道好玩的期望动态规划，只要想到状态，问题就简单了。

设 $f_{i,j,k}$ 为还有 $i$ 个剩1个的盘子，还有 $j$ 个剩2个的盘子，还有 $k$ 个剩3个的盘子时期望的操作次数。

f_{i,j,k}=\frac{n}{i+j+k}+\frac{i}{i+j+k}f_{i-1,j,k}+\frac{j}{i+j+k}f_{i+1,j-1,k}+\frac{k}{i+j+k}f_{i,j+1,k-1}

#include<bits/stdc++.h>
using namespace std;
long long n,a,b,c,x;
double f[305][305][305];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>x;
		if(x==1)a++;
		if(x==2)b++;
		if(x==3)c++;
	}
	for(int k=0;k<=n;k++)
	{	
		for(int j=0;j<=n;j++)
		{
			for(int i=0;i<=n;i++)
			{
				if(i==0&&j==0&&k==0)continue;
				if(i!=0)f[i][j][k]+=i*1.00000/n*f[i-1][j][k];
				if(j!=0)f[i][j][k]+=j*1.00000/n*f[i+1][j-1][k];
				if(k!=0)f[i][j][k]+=k*1.00000/n*f[i][j+1][k-1];
				f[i][j][k]++; 
				f[i][j][k]/=(i+j+k)*1.00000/n;
			}
		}
	}
	printf("%.10lf",f[a][b][c]);
}

K.Stones

对于每个状态，枚举可能选择的石头数量，如果有一个方案是可以保证先手必胜的，那就是先手必胜，否则后手必胜。
设 $f_i$ 表示 $i$ 个石子时是否是先手必胜。

f_i|=f_{i-a_j}(a_j\leq i)

#include<bits/stdc++.h> 
using namespace std;
bool f[100005];
long long n,k,a[100005]; 
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<=k;i++)
	{
		for(int j=1;j<=n&&a[j]<=i;j++)
		{
			f[i]|=!f[i-a[j]];
		}
	}
	if(f[k])
	{
		cout<<"First"<<endl;
	}
	else
	{
		cout<<"Second"<<endl;
	}
}

L.Deque

跟上面那道很像！列出状态之后，套路就一致了，看看公式应该不难理解。
设 $f_{i,j}$ 表示双端队列长度为 $i$ ，对应到原数组，左边界是 $j$ 的先后手之差。

f_{i,j}=\max(-f_{i-1,j}+a_{j+i-1},-f_{i-1,j+1}+a_j);

#include<bits/stdc++.h>
using namespace std; 
long long n,a[3005],sum[3005],f[3005][3005];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];	
		sum[i]=sum[i-1]+a[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j+i-1<=n;j++)
		{
			f[i][j]=max(-f[i-1][j]+a[j+i-1],-f[i-1][j+1]+a[j]);
		}
	}
	cout<<f[n][1]<<endl;
}

M. Candies

这道题是一道典型的前缀和优化DP。
设 $f_{i,j}$ 表示前 $i$ 个人分了 $j$ 颗糖的方案数，那么容易得到：

f_{i,j}=\sum_{k=0}^{a_i}f_{i-1,j-k}

时间复杂度 $O(nk^2)$ ，显然时超。
如何优化？注意到和式内式连续的一段区间和，我们可以用前缀和 $O(1)$ 求出。
于是本题时间复杂度变为 $O(nk)$
注意前缀和要提防数组越界，为此，前缀和数组下标全部往前挪一位。

#include<bits/stdc++.h>
using namespace std; 
long long n,k,a[105],f[105][100005],sum[105][100005];
const long long mod=1e9+7;
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];	
	}
	f[0][0]=1;
	sum[0][1]=1;
	for(int i=1;i<=k+1;i++)sum[0][i]=1;
	for(int i=1;i<=n;i++)
	{
		for(long long j=0;j<=k;j++)
		{
			f[i][j]+=(sum[i-1][j+1]-sum[i-1][max(0ll,j-a[i])]+mod)%mod;
			f[i][j]%=mod;
			sum[i][j+1]=sum[i][j]+f[i][j];
			sum[i][j+1]%=mod;
		}
	}
	cout<<f[n][k]<<endl;
}

N.Slimes

这不就是石子合并吗？是时候祭出远古黑历史了——This

#include<bits/stdc++.h>
using namespace std;
long long dp[505][505],sum[505],n,a[505],mn=1E9;

int main()
{
	memset(dp,127,sizeof(dp));
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		dp[i][i]=0;
	}
	for(int i=1;i<=n;i++)
	{
		sum[i]=sum[i-1]+a[i];
	}
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			int j=i+k-1;
			if(j>n)continue; 
			for(int l=i;l<j;l++)
			{
				dp[i][j]=min(dp[i][j],dp[i][l]+dp[l+1][j]+sum[j]-sum[i-1]);
			}
		} 		
	}
	cout<<dp[1][n]<<endl;
}

DengDuckのBlog

Atcoder 动态规划专项赛解题报告(更新至N题)