几个常见的DP类型.
几个常见的DP类型.
1.路径DP.
例题1.P1216 [USACO1.5][IOI1994]数字三角形 Number
题目传送门
本题每个点路径选择只有两种，很好写dp，具体解释见下面代码。
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int n,dp[N][N],a[N][N];//状态的确立：dp[i][j]表示终点为第i行第j列的最大值
int main(){
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
{
cin>>a[i][j];
if(i==n) //确立初始状态：即最后一行的状态.
dp[i][j]=a[i][j];
}
for(int i=n-1;i>=1;i--)//从下往上递推
for(int j=1;j<=i;j++)
dp[i][j]=max(dp[i+1][j]+a[i][j],dp[i+1][j+1]+a[i][j]);//每个点只能从由下一行的左边一个点或者右边一个点走到
cout<<dp[1][1]<<endl;//反过来想：起点为（1，1）的最大路径 倒过来走终点必为 （1，1）
return 0;
}
2.The least round way
题目传送门：CFB2
思路：考虑对答案的贡献有因数2，5，0.对于0我们只需找到一个标记位置即可（它对答案贡献一个0），对于（2，5）我们只需要比较两者到达终点的较小值，即为0的贡献。
而找2，5，的贡献可以用dp实现。打印可用递归实现。
下面上代码。本题主要考点（数论+路径DP）
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5,inf=0x3f3f3f3f;
int dp[N][N][2],n,a[N][N][2],p;
void Print(int x,int y,int k){ //递归打印 k=1表示向下走 ，k=1向右走
//printf("x=%d,y=%d,k=%d\n",x,y,k);
if(x==1&&y==1){
printf(k?"D":"R");
return ;
}
if(dp[x][y][p]==dp[x][y-1][p]+a[x][y][p])
Print(x,y-1,0);
else Print(x-1,y,1);
if(x!=n||y!=n)
printf(k?"D":"R");
}
int main(){
cin>>n;
int sx,sy,f=0;
for(int i=1;i<=n;i++)
for(int j=1,x;j<=n;j++){
cin>>x;
if(!x) //若找到一个为0的位置 则标记位置
{
sx=i,sy=j,f=1;
}
else { //分别计算因数个数
while(x%2==0) a[i][j][0]++,x/=2;
while(x%5==0) a[i][j][1]++,x/=5;
}
}
for(int i=1;i<=n;i++) //初始化边界
for(int j=0;j<2;j++)
dp[i][0][j]=dp[0][i][j]=inf;
for(int i=0;i<2;i++) //初始化起点
dp[1][1][i]=a[1][1][i];
for(int i=1;i<=n;i++)
for(int j=i==1?2:1;j<=n;j++)
for(int k=0;k<2;k++)
{
dp[i][j][k]=min(dp[i][j-1][k],dp[i-1][j][k])+a[i][j][k];//状态转移
}
int ans=min(dp[n][n][0],dp[n][n][1]);
p=dp[n][n][0]<dp[n][n][1]?0:1;
if(f&&ans>1){ //对于有0的情况打印十分简单
puts("1");
for(int i=1;i<sx;i++)
printf("D");
for(int i=1;i<n;i++)
printf("R");
for(int i=sx;i<n;i++)
printf("D");
puts("");
}
else{
printf("%d\n",ans);
Print(n,n,p);
puts("");
}
return 0;
}
3.过河卒
题目传送门：P1002
路径DP+滚动数组压缩状态 下面上两种代码。
不压缩状态
#include<bits/stdc++.h>
using namespace std;
const int N=30;
typedef long long ll;
int n,m,sx,sy;
bool vis[N][N];
ll dp[N][N];
int d[8][2]={{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1}};
int main(){
cin>>n>>m>>sx>>sy;
n+=2,m+=2,sx+=2,sy+=2;
dp[2][2]=1;
vis[sx][sy]=1;
for(int i=0;i<8;i++)
vis[sx+d[i][0]][sy+d[i][1]]=1;
for(int i=2;i<=n;i++)
for(int j=2;j<=m;j++)
if(!vis[i][j])
dp[i][j]=max(dp[i][j],dp[i][j-1]+dp[i-1][j]);
cout<<dp[n][m]<<endl;
return 0;
}
压缩状态
#include<bits/stdc++.h>
using namespace std;
const int N=30;
typedef long long ll;
int n,m,sx,sy;
bool vis[N][N];
ll dp[N];
int d[8][2]={{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1}};
int main(){
cin>>n>>m>>sx>>sy;
n+=2,m+=2,sx+=2,sy+=2;
dp[2]=1;
vis[sx][sy]=1;
for(int i=0;i<8;i++)
vis[sx+d[i][0]][sy+d[i][1]]=1;
for(int i=2;i<=n;i++)
for(int j=2;j<=m;j++)
if(vis[i][j])
dp[j]=0;
else dp[j]+=dp[j-1];
cout<<dp[m]<<endl;
return 0;
}
简单递推DP.
P2837 [USACO08FEB]Dining Cows B
假设dp[i]为前 i 头 牛的最小修改数。
对第 i 头 牛 进行讨论。如果 第 i 头牛为 2 不用管：dp[ i ]=dp[i -1] ,如果第i头牛为1 又分两种情况：1.如果不用修改，dp[ i ]则等于前面 2 的个数 ， 2.如果要修改，则等于dp[i-1] +1, cnt 可以用一维，由于 dp[ i ] 是由前一个状态的得到，所以空间都可以压缩为 O（1）。下面见代码。
#include<bits/stdc++.h>
using namespace std;
int ans,cnt,n,x;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>x;
x==2?cnt++:ans=min(ans+1,cnt);
}
cout<<ans<<endl;
return 0;
}
状态型dp
P1877 [HAOI2012]音量调节
设dp[ i] [j] 第i首歌能到达的音量 j ，
dp[ i ] [ j ] =1表示该状态能到达 ，反之为0不能到达，最后粗从大到小扫一遍即可。
#include<bits/stdc++.h>
using namespace std;
int dp[1005][1005],a[55];
int main(){
int n,st,mx;
cin>>n>>st>>mx;
for(int i=1;i<=n;i++) cin>>a[i];
dp[0][st]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=mx;j++)
{
if(dp[i-1][j]&&a[i]+j<=mx) dp[i][a[i]+j]=1;
if(dp[i-1][j]&&j-a[i]>=0) dp[i][j-a[i]]=1;
}
for(int i=mx;i>=0;i--)
if(dp[n][i])
{
printf("%d\n",i);
return 0;
}
puts("-1");
return 0;
}