【笔记】入门DP

复习一下近期练习的入门 $DP$ 。巨佬勿喷。$qwq$

重新写一遍练手，加深理解。

代码已经处理，虽然很明显，但请勿未理解就贺 $qwq$

0X00 P1057 [NOIP2008 普及组] 传球游戏

设 $f[i][j]$ 表示传球 $i$ 次后传到第 $j$ 个人的方案数。

设小蛮为 $1$ 号，则初始化 $f[1][n]=1$，$f[1][2]=1$。

转移方程为 $f[i][j]=f[i-1][j-1]+f[i-1][j+1]$ 只需特判 $1$ 的左边变为 $n$ ，$n$ 的右边变为 $1$ 即可。

Code：

#include<bits/stdc++.h>

using namespace std;

int f[35][35],n,m;

int turn(int x){

	return x==n+1?1:(x==0?n:x);

}

int main(){

    scanf("%d%d",&n,&m);

    f[1][n]=f[1][2]=1;

    for(int i=2;i<=m;i++){

    	for(int j=1;j<=n;j++){

    		f[i][j]=f[i-1][turn(j-1)]+f[i-1][turn(j+1)];

		}

	}

	printf("%d",f[m][1]);

    return 73;

}

0X01 P1060 [NOIP2006 普及组] 开心的金明

emmm。背包板题。纯属练手。

Code：

#include<bits/stdc++.h>

using namespace std;

int n,t,v[35],p[35],f[30005];

int main(){

    scanf("%d%d",&t,&n);

    for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&p[i]);

    for(int i=1;i<=n;i++){

    	for(int j=t;j>=v[i];j--) f[j]=max(f[j],f[j-v[i]]+p[i]*v[i]);

	}

	printf("%d",f[t]);

    return 76;

}

0X02 P1509 找啊找啊找GF

不得不说题面有点那啥

二维的背包，因为有 $rmb$ 和 $rp$ 两个条件要考虑。

同时这题也需要两个 $DP$ 数组。一个 $fn[i][j]$ 记录：花费 $i$ 的 $rmb$ ， $j$ 的 $rp$ 可以约的 MM 数量。另一个 $ft[i][j]$ 记录：花费 $i$ 的 $rmb$ ， $j$ 的 $rp$ 最小的花费时间。

因为数组变量太长了看着不舒服，所以我把转移写成了这样：

int t1=fn[j-rmb[i]][k-rp[i]]+1,t2=ft[j-rmb[i]][k-rp[i]]+tim[i];

if(fn[j][k]<t1){      //如果人数更多就一定更优

	fn[j][k]=t1;

	ft[j][k]=t2;

}

if(fn[j][k]==t1) ft[j][k]=min(ft[j][k],t2);    //人数相等看能不能更新ft

幸好我没有 sqybi 这种痛苦

Code：

#include<bits/stdc++.h>

using namespace std;

int n,rmb[105],rp[105],tim[105],m,r;

int fn[105][105],ft[105][105];

int main(){

	scanf("%d",&n);

	for(int i=1;i<=n;i++) scanf("%d%d%d",&rmb[i],&rp[i],&tim[i]);

	scanf("%d%d",&m,&r);

	for(int i=1;i<=n;i++){

		for(int j=m;j>=rmb[i];j--){

			for(int k=r;k>=rp[i];k--){

				int t1=fn[j-rmb[i]][k-rp[i]]+1,t2=ft[j-rmb[i]][k-rp[i]]+tim[i];

				if(fn[j][k]<t1){

					fn[j][k]=t1;

					ft[j][k]=t2;

				}

				if(fn[j][k]==t1) ft[j][k]=min(ft[j][k],t2);

			}

		}

	}

	printf("%d",ft[m][r]);

	return 111;

}

0X03 P1091 [NOIP2004 提高组] 合唱队形

用 $DP$ 跑一遍到每个点的最大上升子序列，再跑一遍倒序的最大下降子序列，最后求可以留下来的 $max$ ，用 $n$ 减掉即可。

用 $f[0][i]$ 表示最大上升子序列， $f[1][i]$ 表示最大下降子序列。因为相等的也会出列，所以注意不加等号。

同时也可以用这个思路过 未加强的导弹拦截。

Code：

#include<bits/stdc++.h>

using namespace std;

int n,a[105],f[2][105],ans;

int main(){

    scanf("%d",&n);

    for(int i=1;i<=n;i++) scanf("%d",&a[i]);

    for(int i=1;i<=n;i++){

    	for(int j=0;j<i;j++){

    		if(a[i]>a[j]) f[0][i]=max(f[0][i],f[0][j]+1);

		}

	}

    for(int i=n;i>=1;i--){

    	for(int j=n+1;j>i;j--){

    		if(a[i]>a[j]) f[1][i]=max(f[1][i],f[1][j]+1);

		}

	}

    for(int i=1;i<=n;i++) ans=max(f[0][i]+f[1][i]-1,ans);

    printf("%d",n-ans);

    return 118;

}

0X04 P1279 字串距离

用 $f[i][j]$ 表示 $A$ 字符串取到前 $i$ 位， $B$ 字符串取到前 $j$ 位时，答案的最小值。

因为求最小值，所以把 $f$ 初始化为极大值。再把 $f[0][0]$ 初始化为 $0$，将所有的 $f[0][i]$ 与 $f[i][0]$ 初始化为 $i \times k$ （$k$ 为空格与字符匹配代价，也就是初始化全是空格的情况）。

转移时分类讨论：

首先考虑一个字符与一个空格匹配的情况，得出 $f[i][j]=min(f[i][j],min(f[i][j-1],f[i-1][j])+k)$。

再考虑两个字符匹配的情况，得出 $f[i][j]=min(f[i][j],f[i-1][j-1]+abs(a[i]-b[j]))$。

空格与空格匹配没有意义。

Code：

#include<bits/stdc++.h>

using namespace std;

string x,y;

int a[2005],b[2005],f[2005][2005],n,m,k;

void init(){

	for(int i=0;i<n;i++) a[i+1]=x[i];

	for(int i=0;i<m;i++) b[i+1]=y[i];

	memset(f,0x3f,sizeof(f));

	f[0][0]=0;

	for(int i=1;i<=max(m,n);i++) f[i][0]=f[0][i]=i*k;

}

int main(){

	cin>>x>>y;

	n=x.size(),m=y.size();

	scanf("%d",&k);

	init();

	for(int i=1;i<=n;i++){

		for(int j=1;j<=m;j++){

			f[i][j]=min(f[i][j],min(f[i][j-1],f[i-1][j])+k);

			f[i][j]=min(f[i][j],f[i-1][j-1]+abs(a[i]-b[j]));

		}

	}

	printf("%d",f[n][m]);

	return 101;

}

注意，双倍经验 ↓ ↓ ↓

0X05 P1140 相似基因

大体思路和上一题相同，只要把匹配的分值改成题目给的表即可。（我才不会告诉你我第一次抄错了）

还要注意一下初始化和转移的小改动。

Code：

#include<bits/stdc++.h>

using namespace std;

int a[105],b[105],f[105][105],n,m;

string x,y;

int t[5][5]{

	{5,-1,-2,-1,-3},

	{-1,5,-3,-2,-4},

	{-2,-3,5,-2,-2},

	{-1,-2,-2,5,-1},

	{-3,-4,-2,-1,0}

};

void turn(int n,int a[],string s){

	for(int i=0;i<n;i++){

		if(s[i]=='A') a[i+1]=0;

		if(s[i]=='C') a[i+1]=1;

		if(s[i]=='G') a[i+1]=2;

		if(s[i]=='T') a[i+1]=3;

	}

}

void init(){

	memset(f,-0x3f,sizeof(f));

	f[0][0]=0;

	for(int i=1;i<=n;i++) f[i][0]=f[i-1][0]+t[a[i]][4];

	for(int i=1;i<=m;i++) f[0][i]=f[0][i-1]+t[4][b[i]];

}

int main(){

	scanf("%d",&n);cin>>x;

	scanf("%d",&m);cin>>y;

	turn(n,a,x);turn(m,b,y);

	init();

	for(int i=1;i<=n;i++){

		for(int j=1;j<=m;j++){

			f[i][j]=max(f[i-1][j]+t[a[i]][4],f[i][j-1]+t[4][b[j]]);

			f[i][j]=max(f[i][j],f[i-1][j-1]+t[a[i]][b[j]]);

		}

	}

	printf("%d",f[n][m]);

	return 67;

}

0X06 P1006 [NOIP2008 提高组] 传纸条

可以看成是走两条不相交的，从 $(1,1)$ 到 $(n,m)$ 的路径的最大值。

设 $f[i][j][x][y]$ 表示第一条走到 $(i,j)$，第二条走到 $(x,y)$ 时的最大值。

转移方程：

$f[i][j][x][y]=$

$max {f[i-1][j][x-1][y],f[i][j-1][x][y-1],

f[i][j-1][x-1][y],f[i-1][j][x][y-1] } $

$+a[i][j]+a[x][y]$

注意，因为两条路不能走到同一个点，所以当 $i=x$ 并且 $j=y$ 时，$f[i][j][x][y]$ 要减掉 $a[i][j]$。

Code：

#include<bits/stdc++.h>

using namespace std;

int f[55][55][55][55],a[55][55],n,m;

int main(){

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++){

    	for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);

	}

	for(int i=1;i<=n;i++){

		for(int j=1;j<=m;j++){

			for(int x=1;x<=n;x++){

				for(int y=1;y<=m;y++){

					int t=max(max(f[i-1][j][x-1][y],f[i][j-1][x][y-1]),

					          max(f[i][j-1][x-1][y],f[i-1][j][x][y-1]));

					f[i][j][x][y]=t+a[i][j]+a[x][y];

					if(i==x&&j==y) f[i][j][x][y]-=a[i][j];

				}

			}

		}

	}

	printf("%d",f[n][m][n][m]);

    return 89;

}

注意，双倍经验 ↓ ↓ ↓

0X07 P1004 [NOIP2000 提高组] 方格取数

前一题题意化简版，范围也更小。改一下读入和输出即可。

#include<bits/stdc++.h>

using namespace std;

int f[15][15][15][15],a[15][15],n;

int u,v,c;

int main(){

    scanf("%d",&n);

    for( ; ; ){

    	scanf("%d%d%d",&u,&v,&c);

    	if(u==0&&v==0&&c==0) break;

    	a[u][v]=c;

	}

	for(int i=1;i<=n;i++){

		for(int j=1;j<=n;j++){

			for(int x=1;x<=n;x++){

				for(int y=1;y<=n;y++){

					int t=max(max(f[i-1][j][x-1][y],f[i][j-1][x][y-1]),

					          max(f[i][j-1][x-1][y],f[i-1][j][x][y-1]));

					f[i][j][x][y]=t+a[i][j]+a[x][y];

					if(i==x&&j==y) f[i][j][x][y]-=a[i][j];

				}

			}

		}

	}

	printf("%d",f[n][n][n][n]);

    return 89;

}

0X08 P1435 [IOI2000]回文字串/[蓝桥杯2016省]密码脱落

设 $f[i][j]$ 表示将从 $i$ 到 $j$ 的字串变为回文最少要插入的字符数。

此时我们只需要枚举区间长度 $k$ 和左端点 $i$，可以计算出右端点 $j=i+k$（直接枚举 $i$ 和 $j$ 是错误的）。

由此可以得出对于区间 $(i,j)$ 的转移方程：

若 $s[i]=s[j]$：$f[i][j]=f[i+1][j-1]$ （不用改）

若 $s[i] \ne s[j]$ ：$f[i][j]=min(f[i+1][j],f[i][j-1])+1$ （取较小值加一次）

Code：

#include<bits/stdc++.h>

using namespace std;

int f[1005][1005],n;

string s;

int main(){

	cin>>s;

	n=s.size();

	for(int i=n;i>=1;i--) s[i]=s[i-1];

	for(int k=1;k<n;k++){

		for(int i=1;i<=n-k;i++){

			int j=i+k;

			if(s[i]==s[j]) f[i][j]=f[i+1][j-1];

			else f[i][j]=min(f[i+1][j],f[i][j-1])+1;

		}

	}

	printf("%d",f[1][n]);

	return 33;

}

巴特西

【笔记】入门DP

0X00 P1057 [NOIP2008 普及组] 传球游戏

0X01 P1060 [NOIP2006 普及组] 开心的金明

0X02 P1509 找啊找啊找GF

0X03 P1091 [NOIP2004 提高组] 合唱队形

0X04 P1279 字串距离

注意，双倍经验 ↓ ↓ ↓

0X05 P1140 相似基因

0X06 P1006 [NOIP2008 提高组] 传纸条

注意，双倍经验 ↓ ↓ ↓

0X07 P1004 [NOIP2000 提高组] 方格取数

0X08 P1435 [IOI2000]回文字串/[蓝桥杯2016省]密码脱落

最新文章

热门文章