Criska

动态规划（一）经典题总结

• 分类: DP • 标签: DP

DP在联赛中很常见啊，所以我把DP经典题做了一下总结，还有洛谷上的一些题，没有写太多，待更新

1.洛谷1006 传纸条

  • 转化一下思路，可以把来回两条路变成从同一个起点开始互不交叉的两条路，然后通过一个四维数组（可以优化成三维但是我木有学= =）进行记录。
    因为每次只有四种可能，分别是f[i-1][j][k-1][l]，f[i-1][j][k][l-1]，f[i][j-1][k-1][l]，f[i][j-1][k][l-1]，记录最大值就可以了~

  • 还有一道几乎一模一样的题洛谷1004方格取数小伙伴们当练手好啦

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<cstdio>
using namespace std;
int m,n,a[51][51],f[51][51][51][51];
int main()
{
	scanf("%d%d",&m,&n);
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
		scanf("%d",&a[i][j]);
	for(int i=1;i<=m;++i)
		for(int j=1;j<=n;++j)
			for(int k=1;k<=m;++k)
				for(int l=1;l<=n;++l)
					{
						
						int s=0;
						if(i-1!=k-1&&j!=l)
						s=max(s,f[i-1][j][k-1][l]);
						
						if(i-1!=k&&j!=l-1)
						s=max(s,f[i-1][j][k][l-1]);
						if(i!=k-1&&j-1!=l)
						s=max(s,f[i][j-1][k-1][l]);
						if(i!=k&&j-1!=l-1)
						s=max(s,f[i][j-1][k][l-1]);
						f[i][j][k][l]=s+a[i][j]+a[k][l];
					}
	cout<<f[m][n][m][n];
	return 0;
}

2.导弹拦截

  • 超级经典的一道DP题啊，反正我的DP入门题（还是贪心？？我忘了）是它→ →

  • 直接附上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<iostream>
#include<cstdio>
using namespace std;
int n=1,a[1000000][3],m=0,b[10000],r=1; 
int main()
{
	while(cin>>a[n][1])n++;
	n=n-1;
	for(int i=1;i<=n;++i)
	{
		a[i][2]=1;	
	}
	for(int i=n-1;i>0;--i)
	{
		for(int j=i+1;j<=n;++j)
		{
			if(a[i][1]>=a[j][1]&&a[i][2]<=a[j][2])
			a[i][2]=a[j][2]+1;
		}
	}
	for(int i=1;i<=n;++i)
	{
		if(a[i][2]>m)
		m=a[i][2];
	}
	
	b[1]=a[n][1];
	for(int i=n;i>0;--i)
	{
		for(int j=1;j<=r;++j)
		{
			if(j==r&&a[i][1]<b[j])
			{
				r++;
				b[r]=a[i][1];
				break;
			}
			if(a[i][1]>b[j])
			{
				b[j]=a[i][1];
				break;
			}
		}
		
	}
	cout<<m<<endl<<r;
	return 0;
}

3.乘积最大

  • 这也是一年noip的原题好像= =
    用 f [ i ] [ p ] 表示前 i 个数中插入 p 个字符串所得乘积的最大值，然后枚举1~i之间的 j值，表示新的乘号插入的位置
  • 状态转移方程为f [ i ] [ p ] = max ( f [ i ] [ p ] , f [ j ] [ p - 1 ] * a [ j + 1 ] [ i ] ) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#include<cstdio>
using namespace std;
const int N=2000;
int n,k,c[N]={0};
int f[500][500],a[500][500];
char s[N];
int ping(int a)
{
	long long  sum=1;
	for(int i=1;i<=a;++i)
		sum=sum*10;
	return sum;
}
int main()
{
	scanf("%d%d",&n,&k);
	scanf("%s",s);
	for(int i=0;i<n;++i)
	{
		c[i+1]=s[i]-48+c[i]*10;
		//f[i+1][0]=c[i+1];
	}
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			a[i][j]=c[j]-c[i-1]*ping(j-i+1);
	for(int i=1;i<=n;++i)
		f[i][0]=a[1][i];
	for(int p=1;p<=k;++p)
		for(int i=p+1;i<=n;++i)
			for(int j=p;j<i;++j)
			{
				f[i][p]=max(f[i][p],f[j][p-1]*a[j+1][i]);
			}
	cout<<f[n][k];
	return 0;
}

4.合唱队形

  • 这道题考的就是最长不下降子序列啦，不过要稍稍修改一下，一遍是正着搜，搜的是 最长上升子序列，一遍是反着搜，搜的是最长不下降子序列，这样用f [ i ] 和g [ i ]记录每一个点的前面最多有多少个数比它大，后面有多少个数比它小。
  • 需要注意的是，最中间的那个人注定会被多记录一次，所以结果要减1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
#include<cstdio>
using namespace std;
int n,a[1010],f[1010],g[1010];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;++i)
	{
		f[i]=1;
		for(int j=i-1;j>=1;--j)
		{
			if(a[i]>a[j]&&f[j]+1>f[i]) 
			f[i]=f[j]+1;
		}
		//if(l==0) f[i]=1;
				
	}
	//int ma=0;
	//for(int i=1;i<=n;++i) 
	//if(f[i]>ma) ma=f[i];
	
	for(int i=n;i>=1;--i)
	{
		g[i]=1;
		for(int j=i+1;j<=n;++j)	
		{
			if(a[j]<a[i]&&g[j]+1>g[i])
			g[i]=g[j]+1;
		}	
		//if(l==0) g[i]=1;
	}
	int mi=0;
	for(int i=1;i<=n;++i) 
	if(g[i]+f[i]>mi) mi=g[i]+f[i];
	cout<<n-mi+1;
	return 0;
}

5.乌龟棋

  • 这一道题首先要注意的是，审题，一共只有四张牌，所以以这四张牌为出发点写状态转移方程，用f[i][j][k][p]表示用了i张第一种牌，j张第二种牌……之类的，因为只要确定了牌数，就确定了他走到的位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
#include<cstdio>
using namespace std;
const int N=2000;
int n,m;
int f[50][50][50][50],a[500],b;
int i1,j1,k1,p1;
int ping(int a)
{
	long long  sum=1;
	for(int i=1;i<=a;++i)
		sum=sum*10;
	return sum;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
		scanf("%d",&a[i]);
	for(int i=1;i<=m;++i)
	{
		scanf("%d",&b);
		if(b==1) i1++;
		if(b==2) j1++;
		if(b==3) k1++;
		if(b==4) p1++;
	}
		
	f[0][0][0][0]=a[1];
	for(int i=0;i<=i1;++i)
	for(int j=0;j<=j1;++j)
	for(int k=0;k<=k1;++k)
	for(int p=0;p<=p1;++p)
	{
		int ma=0;
		if(i!=0) 
		ma=max(ma,f[i-1][j][k][p]);
		if(j!=0) 
		ma=max(ma,f[i][j-1][k][p]);
		if(k!=0) 
		ma=max(ma,f[i][j][k-1][p]);
		if(p!=0) 
		ma=max(ma,f[i][j][k][p-1]);
		f[i][j][k][p]=ma+a[1+i+j*2+k*3+p*4];
	}
	cout<<f[i1][j1][k1][p1];
	return 0;
}

6.小奇挖矿

【题目背景】
小奇要开采一些矿物，它驾驶着一台带有钻头（初始能力值w）的飞船，按既定路线依次飞过喵星系的n个星球。

【问题描述】
星球分为2类：资源型和维修型。

1.资源型：含矿物质量a[i]，若选择开采，则得到a[i]*p的金钱，之后钻头损耗k%，即p=p*(1-0.01k)

2.维修型：维护费用b[i]，若选择维修，则支付b[i]*p的金钱，之后钻头修复c%，即p=p*(1+0.01c)

（p为钻头当前能力值）

注：维修后钻头的能力值可以超过初始值
请你帮它决策最大化这个收入

【输入格式】
第一行4个整数n，k，c，w。
以下n行，每行2个整数type，x。
type为1则代表其为资源型星球，x为其矿物质含量a[i]；
type为2则代表其为维修型星球，x为其维护费用b[i]；

【输出格式】
输出一行一个实数（保留两位小数），表示要求的结果。

【样例输入】
5 50 50 10
1 10
1 20
2 10
2 20
1 30

【样例输出】
375.00

【数据范围】
对于30%的数据 n<=100
对于50%的数据 n<=1000，k=100
对于100%的数据 n<=100000，0<=k，c，w，a[i]，b[i]<=100
保证答案不超过10^9

  • 黄学长出的题果然不一样！
  • 辛辛苦苦写了爆搜结果爆零了哈哈……然后看了一眼std……哇……好简单……但是就是想不到……哭晕QAQ
  • 首先可以想到的是，因为星球路线是已经确定好的，所以每次向后挖的时候只会对后面的结果产生影响，而对前面的不会产生影响，所以从后往前进行DP。
  • 其次，我们最后要求的是金钱最大值，其实和钻头初始或者变化值没有关系，每次影响的只有k值，所以我们不妨考虑一下乘法分配率的思想，从n进行DP，动态转移方程为ans=max(ans,ans*k+a[i])或者ans=max(ans,ans*\c-a[i])，而最终的结果只需要将ans*w就可以了。
    （果然DP这种东西只可意会不可言传= =）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<cstdio>
using namespace std;
const int N=200000;
int n,a[N],b[N];
double c,w,k,ans=0;
int main()
{
	freopen("explo.in","r",stdin);
	freopen("explo.out","w",stdout);
	scanf("%d",&n);
	cin>>k>>c>>w;
	k=1-k*0.01;
	c=1+c*0.01;
	int cnt=1,h;
	for(int i=1;i<=n;++i)
	{
		scanf("%d%d",&h,&a[i]);
		b[i]=h;
	}
	for(int i=n;i>=1;--i)
	{
		if(b[i]==1)
		ans=max(ans,ans*k+a[i]);
		if(b[i]==2)
		ans=max(ans,ans*c-a[i]);
	}
	printf("%.2lf",ans*w);
	return 0;
}

7.子串

一道恶心至极的DP题，还有第一次使用的滚动数组= =
好好研究吧^_^

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
#include<cstdio>
using namespace std;
const int p=1000000007;
int la,lb,K,f[3][201][201],g[3][201][201];
char a[1010],b[250];
int main()
{
	freopen("substring.in","r",stdin);
	freopen("substring.out","w",stdout);
	scanf("%d%d%d",&la,&lb,&K);
	scanf("%s",a+1);
	scanf("%s",b+1);
	f[0][0][0]=g[0][0][0]=1;
	for(int i=1;i<=la;++i)
	{
		f[i%2][0][0]=1;
		g[i%2][0][0]=1;
		for(int j=1;j<=lb;++j)
		{
			for(int k=1;k<=K;++k)
			{
				if(a[i]==b[j])
				{					
					f[i%2][j][k]=f[(i-1)%2][j-1][k];
					f[i%2][j][k]+=g[(i-1)%2][j-1][k-1];
					f[i%2][j][k]%=p;
					g[i%2][j][k]=(g[(i-1)%2][j][k]+f[i%2][j][k])%p;
				}
				else
				{
					f[i%2][j][k]=0;
					g[i%2][j][k]=g[(i-1)%2][j][k]%p;
				}
			}
		}
	}
	printf("%d",g[la%2][lb][K]%p);
	return 0;
}