openjudge动态规划

OI&ACM, DP
  1. 1.1775 采药
  2. 2.1944 吃糖果
  3. 3.6252 带通配符的字符串匹配
  4. 4.666 放苹果
  5. 5.7614 最低通行费
  6. 6.7624 山区建小学
  7. 7.7625 三角形最佳路径问题
  8. 8.7627 鸡蛋的硬度
  9. 9.8780 拦截导弹
  10. 10.8782 乘积最大
  11. 11.8785 装箱问题
  12. 12.8786 方格取数
  13. 13.8787 数的划分
  14. 14.90 滑雪

1.1775 采药

辰辰是个很有潜能、天资聪颖的孩子，他的梦想是称为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？

裸的01背包 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<cstdio>
using namespace std;
int T,m,t[101],w[101],f[101][1001];
int main()
{
	scanf("%d%d",&T,&m);
	for(int i=1;i<=m;i++)
	  scanf("%d%d",&t[i],&w[i]);
	for(int i=1;i<=m;i++)
	  for(int j=0;j<=T;j++)
	  {
	  	f[i][j]=f[i-1][j];
	  	if(j>=t[i]&&f[i-1][j-t[i]]+w[i]>f[i][j])
	      f[i][j]=f[i-1][j-t[i]]+w[i];
	  }
	printf("%d",f[m][T]);
}

2.1944 吃糖果

名名的妈妈从外地出差回来，带了一盒好吃又精美的巧克力给名名（盒内共有 N 块巧克力，20>N>0）。妈妈告诉名名每天可以吃一块或者两块巧克力。假设名名每天都吃巧克力，问名名共有多少种不同的吃完巧克力的方案。例如：如果N=1，则名名第1天就吃掉它，共有1种方案；如果N=2，则名名可以第1天吃1块，第2天吃1块，也可以第1天吃2块，共有2种方案；如果N=3，则名名第1天可以吃1块，剩2块，也可以第1天吃2块剩1块，所以名名共有2+1=3种方案；如果N=4，则名名可以第1天吃1块，剩3块，也可以第1天吃2块，剩2块，共有3+2=5种方案。现在给定N，请你写程序求出名名吃巧克力的方案数目。

这居然是个斐波那契。。。
用矩阵乘法也不错（懒得写了）
拓展：若每天可以吃1~a块巧克力，则\(f[0]=1\),\(f[i]=\sum\limits_{i-a>0}^{0≤k≤i-1} f[k]\)

1
2
3
4
5
6
7
8
9
10
11
#include<cstdio>
using namespace std;
int n,f[21];
int main()
{
	scanf("%d",&n);
	f[0]=f[1]=1;
	for(int i=2;i<=n;i++)
	  f[i]=f[i-1]+f[i-2];
	printf("%d",f[n]);
}

3.6252 带通配符的字符串匹配

通配符是一类键盘字符，当我们不知道真正字符或者不想键入完整名字时，常常使用通配符代替一个或多个真正字符。通配符有问号( ? )和星号( * )等，其中，“?”可以代替一个字符，而“*”可以代替零个或多个字符。
你的任务是，给出一个带有通配符的字符串和一个不带通配符的字符串，判断他们是否能够匹配。
例如，1?456 可以匹配 12456、13456、1a456，但是却不能够匹配23456、1aa456；
2*77?8可以匹配 24457798、237708、27798。

一不小心写了个搜索 

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
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
char s1[21],s2[21],yes,len1,len2;
void search(int x,int y)
{
	if(yes||x>len1||x+y>len2) return;
	if(x==len1&&x+y==len2)
	{
		yes=1;printf("matched");return;
	}
	if(s1[x]=='?')  search(x+1,y);
	else if(s1[x]=='*')
	{
		for(int i=-1;x+y+i<=len2;i++)
		  search(x+1,y+i);
	}
	else if(s1[x]==s2[x+y]) search(x+1,y);
}
int main()
{
	cin>>s1>>s2;
	len1=strlen(s1);len2=strlen(s2);
	search(0,0);
	if(!yes) printf("not matched");
}

dp显然比搜索快多了，f[i][j]表示s1中的第i个和s2中的第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
#include<cstdio>
#include<cstring>
using namespace std;
char s1[21],s2[21];
int len1,len2,x,f[21][21];
int main()
{
	scanf("%s%s",s1+1,s2+1);
	len1=strlen(s1+1);len2=strlen(s2+1);
	f[0][0]=1;
	for(int i=1;i<=len1;i++)
	{
		if(s1[i]=='*')
		 {
		 	x=0;
		 	while(!f[i-1][x]) x++;
		 	for(int j=x;j<=len2;j++)  f[i][j]=1;
		 }
		else if(s1[i]=='?') 
		 {
		 	for(int j=1;j<=len2;j++)
		      if(f[i-1][j-1]) f[i][j]=1;
		 } 
		else
		 {
		 	for(int j=1;j<=len2;j++)
		      if(s1[i]==s2[j]&&f[i-1][j-1]) f[i][j]=1;
		 }
	}
	if(f[len1][len2]) printf("matched");
	else printf("not matched");
}

4.666 放苹果

把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。

脑残的搜索 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<cstdio>
using namespace std;
int n,m,tot,T;
void search(int num,int pre,int sheng)
{
	if(num==n) {tot++;return;}
	for(int i=pre;i<=sheng/(n-num+1);i++)
	  search(num+1,i,sheng-i);
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&m,&n);
		tot=0;
		search(1,0,m);
		printf("%d\n",tot);
	}
}

简单的dp，f[i][j]表示i个苹果，j个盘子的放法
f[i][j]=f[i][j-1]+f[i-j][j] 具体见13题 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<cstdio>
using namespace std;
int t,m,n,f[11][11];
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&m,&n);
		f[0][0]=1;
		for(int i=0;i<=m;i++)
		  for(int j=1;j<=n;j++)
		  {
		  	f[i][j]=f[i][j-1];
		  	if(j<=i) f[i][j]+=f[i-j][j];
		  }
		printf("%d\n",f[m][n]);
	}
}

5.7614 最低通行费

一个商人穿过一个 N*N 的正方形的网格，去参加一个非常重要的商务活动。他要从网格的左上角进，右下角出。每穿越中间1个小方格，都要花费1个单位时间。商人必须在(2N-1)个单位时间穿越出去。而在经过中间的每个小方格时，都需要缴纳一定的费用。
这个商人期望在规定时间内用最少费用穿越出去。请问至少需要多少费用？
注意：不能对角穿越各个小方格（即，只能向上下左右四个方向移动且不能离开网格）。

2N-1表示他只能向右或者向下走，不能拐回去
f[i][j]=min(f[i-1][j],f[i][j-1])+g[i][j]; 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,g[101][101],f[101][101];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++)
	    scanf("%d",&g[i][j]);
	memset(f,0x7f,sizeof(f));
	f[0][1]=f[1][0]=0;
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++)
	    f[i][j]=min(f[i-1][j],f[i][j-1])+g[i][j];
	printf("%d",f[n][n]);
}

6.7624 山区建小学

政府在某山区修建了一条道路，恰好穿越总共m个村庄的每个村庄一次，没有回路或交叉，任意两个村庄只能通过这条路来往。已知任意两个相邻的村庄之间的距离为di（为正整数），其中，0 < i < m。为了提高山区的文化素质，政府又决定从m个村中选择n个村建小学（设 0 < n < = m < 500 ）。请根据给定的m、n以及所有相邻村庄的距离，选择在哪些村庄建小学，才使得所有村到最近小学的距离总和最小，计算最小值。

sum1[i][j]表示i~j村中的人都到i的总距离
f[i][j]表示前i个村庄，在修了j个学校的最小距离
可知在i~j的村庄中，在(i+j)/2建学校总距离最小 

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
#include<cstring>
#include<cstdio>
using namespace std;
int x,y,n,m,f[501][501],sum[501],sum1[501][501];
int main()
{
	memset(f,0x7f,sizeof(f));
	scanf("%d%d",&m,&n);
	for(int i=2;i<=m;i++)
	  scanf("%d",&x),sum[i]=sum[i-1]+x;
	for(int i=1;i<=m;i++)
	  {
	  	for(int j=i+1;j<=m;j++) sum1[i][j]=sum1[i][j-1]+sum[j]-sum[i];
	  	for(int j=i-1;j>=1;j--) sum1[i][j]=sum1[i][j+1]+sum[i]-sum[j];
	  }
	f[0][0]=0;
	for(int i=1;i<=m;i++)
	  for(int j=1;j<=i&&j<=n;j++)
	    for(int k=j-1;k<=i-1;k++)
	    {
	    	x=(k+1+i)/2;
	    	y=sum1[x][k+1]+sum1[x][i]+f[k][j-1];
	    	if(y<f[i][j]) f[i][j]=y;
	    } 
	printf("%d",f[m][n]);
}

7.7625 三角形最佳路径问题

如下所示的由正整数数字构成的三角形:
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，和最大的路径称为最佳路径。你的任务就是求出最佳路径上的数字之和。
注意：路径上的每一步只能从一个数走到下一层上和它最近的下边（正下方）的数或者右边（右下方）的数。

这不是dp入门题嘛，我就不说啥了吧 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
#include<cstdio>
using namespace std;
int n,maxx,f[101][101];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=i;j++)
	    {
	    	scanf("%d",&f[i][j]);
	    	f[i][j]+=max(f[i-1][j-1],f[i-1][j]);
	    }
	for(int i=1;i<=n;i++)
	  if(maxx<f[n][i]) maxx=f[n][i];
	printf("%d",maxx);
}

8.7627 鸡蛋的硬度

最近XX公司举办了一个奇怪的比赛：鸡蛋硬度之王争霸赛。参赛者是来自世 界各地的母鸡，比赛的内容是看谁下的蛋最硬，更奇怪的是XX公司并不使用什么精密仪器来测量蛋的硬度，他们采用了一种最老土的办法--从高度扔鸡蛋--来 测试鸡蛋的硬度，如果一次母鸡下的蛋从高楼的第a层摔下来没摔破，但是从a+1层摔下来时摔破了，那么就说这只母鸡的鸡蛋的硬度是a。你当然可以找出各种 理由说明这种方法不科学，比如同一只母鸡下的蛋硬度可能不一样等等，但是这不影响XX公司的争霸赛，因为他们只是为了吸引大家的眼球，一个个鸡蛋从100 层的高楼上掉下来的时候，这情景还是能吸引很多人驻足观看的，当然，XX公司也绝不会忘记在高楼上挂一条幅，写上“XX公司”的字样--这比赛不过是XX 公司的一个另类广告而已。
勤于思考的小A总是能从一件事情中发现一个数学问题，这件事也不例外。“假如有很多同样硬度的鸡蛋，那么我可以用二分的办法用最少的次数测出鸡蛋 的硬度”，小A对自己的这个结论感到很满意，不过很快麻烦来了，“但是，假如我的鸡蛋不够用呢，比如我只有1个鸡蛋，那么我就不得不从第1层楼开始一层一 层的扔，最坏情况下我要扔100次。如果有2个鸡蛋，那么就从2层楼开始的地方扔……等等，不对，好像应该从1/3的地方开始扔才对，嗯，好像也不一定 啊……3个鸡蛋怎么办，4个，5个，更多呢……”，和往常一样，小A又陷入了一个思维僵局，与其说他是勤于思考，不如说他是喜欢自找麻烦。
好吧，既然麻烦来了，就得有人去解决，小A的麻烦就靠你来解决了

f[i][j]表示有i个鸡蛋，j层楼的次数
从第t层扔下一个鸡蛋，如果碎了，还有i-1个鸡蛋，f[i-1][t-1]次；
如果没碎，上面还有j-k层，需要f[i][j-t]层。
所以f[i][j]=min(1+max(f[i-1][t-1],f[i][j-t])
初始f[1][k]=k
详见 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m,f[11][101];
int main()
{
	for(int i=1;i<=100;i++) f[1][i]=i;
	for(int i=2;i<=10;i++)
	  for(int j=1;j<=100;j++)
	  {
		f[i][j]=1+max(f[i-1][0],f[i][j-1]);
		for(int t=2;t<=j;t++)
		  f[i][j]=min(f[i][j],1+max(f[i-1][t-1],f[i][j-t]));
	  }
	while(scanf("%d%d",&n,&m)==2)
	  printf("%d\n",f[m][n]);
}

9.8780 拦截导弹

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹。

a[i]表示1~i最长不上升子序列的长度
a[i]=max(a[j])+1 ( j < i && h[j] >= h[i] ) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<cstdio>
using namespace std;
int n,maxx,ans,h[16],a[16];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	  scanf("%d",&h[i]);
	for(int i=1;i<=n;i++)
	{
		maxx=0;
		for(int j=1;j<i;j++)
		  if(h[i]<=h[j]&&a[j]>maxx) maxx=a[j];
		a[i]=maxx+1;
		if(a[i]>ans) ans=a[i];
	}
	printf("%d",ans);
}

10.8782 乘积最大

今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：
设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。
同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：
有一个数字串：312，当N=3，K=1时会有以下两种分法：
1) 3*12=36
2) 31*2=62
这时，符合题目要求的结果是：31*2=62
现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。

num[i][j]表示从i到j的数
f[i][k]表示1~i中加k个乘号的最大值
f[i][k]=max(f[j][k-1]*num[j+1][i]) (j < 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
#include<iostream>
#include<cstdio>
using namespace std;
int n,K,x,num[41][41],f[41][7];
char c;
int main()
{
	scanf("%d%d",&n,&K);
	for(int i=1;i<=n;i++)
	{
		cin>>c;
		x=c-'0';
		for(int j=1;j<=i;j++)
		  num[j][i]=num[j][i-1]*10+x;
		f[i][0]=num[1][i];
	}
	for(int i=1;i<=n;i++)
	  for(int k=1;k<=K;k++)
	    for(int j=1;j<i;j++)
	    {
	    	x=f[j][k-1]*num[j+1][i];
	    	if(x>f[i][k]) f[i][k]=x;
	    }
	printf("%d",f[n][K]);

11.8785 装箱问题

有一个箱子容量为V（正整数，0<=v<=20000），同时有n个物品（0< n<=30），每个物品有一个体积（正整数）。
要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。求最小剩余。

可以当做价值与体积相等的01背包 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>
#include<cstdio>
using namespace std;
int v,n,x,y,f[20001];
int main()
{
	scanf("%d%d",&v,&n);
	for(int i=1;i<=n;i++)
	  {
	  	scanf("%d",&x);
	    for(int j=v;j>=x;j--)
	  	  f[j]=max(f[j],f[j-x]+x);
	  }
	printf("%d",v-f[v]);
}

才开始写的f[i][j]表示前i个物品，能不能装成容量为j 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<cstdio>
using namespace std;
int v,n,ans,a[31];
bool f[31][20001];
int main()
{
	scanf("%d%d",&v,&n);
	for(int i=1;i<=n;i++)
	  scanf("%d",&a[i]),f[i][a[i]]=1;
	for(int i=1;i<=n;i++)
	  for(int j=0;j<=v;j++)
	  	{
	  		if(f[i-1][j]) f[i][j]=f[i-1][j];
		    if(j-a[i]>=0&&!f[i][j])
			  f[i][j]=f[i-1][j-a[i]];
	  	}
	while(!f[n][v-ans]) ans++;
	printf("%d",ans);
}

12.8786 方格取数

设有N*N的方格图(N<=10),我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示：
某人从图的左上角的A点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。 此人从A点到B 点共走两次，试找出2条这样的路径，使得取得的数之和为最大。

三维dp，f[a][b][c]表示第一个人走到(a,b)，第二个人走到(c,a+b-c)的和
（因为他们走的长度相同，即a+b=c+d，∴d=a+b-c.）
有四种转移方法: f[a-1][b][c-1], f[a-1][b][c], f[a][b-1][c-1], f[a][b-1][c]
如果两个人走到同一个点上的话，加上这个点的值
如果不是不是一个点，都加上 

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
#include<iostream>
#include<cstdio>
using namespace std;
int n,x,y,z,g[11][11],f[11][11][11];
int main()
{
	scanf("%d",&n);
	for(;;)
	{
		scanf("%d%d%d",&x,&y,&z);
		if(!x&&!y&&!z) break;
		g[x][y]=z;
	}
	for(int a=1;a<=n;a++)
	 for(int b=1;b<=n;b++)
	  for(int c=max(1,a+b-n);c<=n&&c<=a+b-1;c++)
	   {
	   	 x=0;
	   	 if(f[a-1][b][c-1]>x) x=f[a-1][b][c-1];
	   	 if(f[a-1][b][c]>x) x=f[a-1][b][c];
	   	 if(f[a][b-1][c-1]>x) x=f[a][b-1][c-1];
	   	 if(f[a][b-1][c]>x) x=f[a][b-1][c];
	   	 if(a==c) f[a][b][c]=x+g[a][b];
	   	 else f[a][b][c]=x+g[a][b]+g[c][a+b-c];
	   }
	printf("%d",f[n][n][n]);
}

13.8787 数的划分

将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。
例如：n=7，k=3，下面三种分法被认为是相同的。
1，1，5； 1，5，1； 5，1，1；
问有多少种不同的分法。 输出：一个整数，即不同的分法。

第四题放苹果为拆成非负整数的情况
f[i][j]表示数i拆成j个数的方法
f[i][j]=f[i-j][j]+f[i-1][j-1]
分成两种情况：
1.不包括1的情况，即把每个位子上都先放上1，再把剩下的i-j个放到j个里面，f[i-j][j]
2.包括1的情况，即第一个数是1，剩下的i-1个数放到j-1个位子里面，f[i-1][j-1]
类似整数划分问题 

1
2
3
4
5
6
7
8
9
10
11
12
#include<cstdio>
using namespace std;
int n,k,f[206][7];
int main()
{
	scanf("%d%d",&n,&k);
	f[1][1]=1;
	for(int i=2;i<=n;i++)
	  for(int j=1;j<=k&&j<=i;j++)
	  	f[i][j]=f[i-j][j]+f[i-1][j-1];
	printf("%d",f[n][k]);
}

14.90 滑雪

Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-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
#include<cstring>
#include<cstdio>
using namespace std;
int a[][2]={{0,-1},{0,1},{-1,0},{1,0}};
int n,m,ans,t,g[101][101],f[101][101];
int dfs(int x,int y)
{
	if(f[x][y]!=-1) return f[x][y];
	int maxx=1;
	for(int i=0;i<4;i++)
	{
		int xx=x+a[i][0],yy=y+a[i][1];
		if(xx>0&&xx<=n&&yy>0&&yy<=n&&g[x][y]<g[xx][yy])
		{
			int b=dfs(xx,yy)+1;
			if(b>maxx) maxx=b;
		}
	}
	f[x][y]=maxx;
	return maxx;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++)
	    scanf("%d",&g[i][j]);
	memset(f,-1,sizeof(f));
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++)
	    {
	    	int x=dfs(i,j);
	    	if(x>ans) ans=x;
	    }
	printf("%d",ans);
}
DP