线性dp总结+例题

动态规划：解决多阶段决策性问题最优解（计数）的方法
1.条件：重叠子问题（每个点面对的决策相同）
2.最优子结构
3.无后效性：即历史对现在没有影响。
4.一般步骤：a.确定状态（原问题+子问题）
b.转移方程
c.优化

eg1.最长不下降子序列

最少拦截系统 HDU - 1257 hdu-1257
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹.
怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.
Input
输入若干组数据.每组数据包括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔)
Output
对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统.
Sample Input
8 389 207 155 300 299 170 158 65
Sample Output
2
题意求有多少个下降子序列，实际求有多少不下降子序列。

#include<cstdio>
#include<iostream>
using namespace std;

int main()
{
    int n,i,j,num,h[1000],max[1000];
    while(~scanf("%d",&n))
    {
        num=0;
        for(i=0;i<n;++i)
        {
            scanf("%d",&h[i]);
            max[i]=1;
        }
        for(i=1;i<n;++i)
            for(j=0;j<i;++j)
            {
                if(h[j]<=h[i]&&max[j]+1>max[i]){
				
                    max[i]=max[j]+1;
                    //cout<<num<<" "<<max[i]<<endl;
                }
                if(num<max[i])
                    num=max[i];
            }
        printf("%d\n",num);
    }
    return 0;
}
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

eg2.求最大对称子矩阵

Phalanx HDU - 2859 hdu-2859

Today is army day, but the servicemen are busy with the phalanx for the celebration of the 60th anniversary of the PRC.
A phalanx is a matrix of size nn, each element is a character (a~z or A~Z), standing for the military branch of the servicemen on that position.
For some special requirement it has to find out the size of the max symmetrical sub-array. And with no doubt, the Central Military Committee gave this task to ALPCs.
A symmetrical matrix is such a matrix that it is symmetrical by the “left-down to right-up” line. The element on the corresponding place should be the same. For example, here is a 33 symmetrical matrix:
cbx
cpb
zcc
Input
There are several test cases in the input file. Each case starts with an integer n (0<n<=1000), followed by n lines which has n character. There won’t be any blank spaces between characters or the end of line. The input file is ended with a 0.
Output
Each test case output one line, the size of the maximum symmetrical sub- matrix.
Sample Input
3
abx
cyb
zca
4
zaba
cbab
abbc
cacq
0
Sample Output
3
3

dp[i][j]表示以（i，j）为左下角的对称子矩阵的长度，由右上角向左下角推，只需判断新扩展的点是否对称。
初始化：每个点都是一个矩阵，dp[1][i]=dp[i][n]=1.
注意：当出现不同时立即break。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int dp[1005][1005];
char a[1005][1005];
int main(){
	int n;
	while(~scanf("%d",&n)){
		if(n==0)break;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				cin>>a[i][j];
			}
		}
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++){
			dp[1][i]=dp[i][n]=1;
		}
		int ans=1;
		for(int i=2;i<=n;i++){
			for(int j=n-1;j>=1;j--){
				int k=dp[i-1][j+1];
				for(int x=0;x<=k;x++){
					if(a[i][j+x]==a[i-x][j])dp[i][j]++;
					else break;
				}
				ans=max(ans,dp[i][j]);
			}
		}
	
		printf("%d\n",ans);
	}
	return 0;
}
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

eg3.记忆化搜索

滑雪 POJ - 1088 poj-1088
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更长。事实上，这是最长的一条。
Input
输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。
Output
输出最长区域的长度。
Sample Input
5 5
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
Sample Output
25
每个点都算一遍会超时，所以将算过的点记录下来，当再出现时直接return。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[101][101],dp[101][101];
int r,c;
int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int judge(int xx,int yy){
	if(xx>=1&&xx<=r&&yy>=1&&yy<=c)return 1;
	return 0;
}
int f(int x,int y){
	if(dp[x][y])return dp[x][y];
	for(int i=0;i<4;i++){
		int tx=x+dir[i][0];
		int ty=y+dir[i][1];
		if(judge(tx,ty)){
		
		if(a[x][y]>a[tx][ty]){
			int tem=f(tx,ty);
			dp[x][y]=dp[x][y]>tem?dp[x][y]:tem+1;
		}
	}
	}
	return dp[x][y];
	
}
int main(){
//	int r,c;
	scanf("%d%d",&r,&c);
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			scanf("%d",&a[i][j]);
		}
	}
	memset(dp,0,sizeof(dp));
	int ans=0;
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			ans=max(ans,f(i,j));
		}
	}
	cout<<ans+1<<endl;
	return 0; 
}
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

eg4.最大工作效率

Milking Time POJ - 3616 poj-3616

Bessie is such a hard-working cow. In fact, she is so focused on maximizing her productivity that she decides to schedule her next N (1 ≤ N ≤ 1,000,000) hours (conveniently labeled 0…N-1) so that she produces as much milk as possible.

Farmer John has a list of M (1 ≤ M ≤ 1,000) possibly overlapping intervals in which he is available for milking. Each interval i has a starting hour (0 ≤ starting_houri ≤ N), an ending hour (starting_houri < ending_houri ≤ N), and a corresponding efficiency (1 ≤ efficiencyi ≤ 1,000,000) which indicates how many gallons of milk that he can get out of Bessie in that interval. Farmer John starts and stops milking at the beginning of the starting hour and ending hour, respectively. When being milked, Bessie must be milked through an entire interval.

Even Bessie has her limitations, though. After being milked during any interval, she must rest R (1 ≤ R ≤ N) hours before she can start milking again. Given Farmer Johns list of intervals, determine the maximum amount of milk that Bessie can produce in the N hours.

Input

• Line 1: Three space-separated integers: N, M, and R
• Lines 2…M+1: Line i+1 describes FJ’s ith milking interval withthree space-separated integers: starting_houri , ending_houri , and efficiencyi

Output

• Line 1: The maximum number of gallons of milk that Bessie can product in the N hours

Sample Input
12 4 2
1 2 8
10 12 19
3 6 24
7 10 31
Sample Output
43
题意：有n头奶牛，分别给出他们的开始时间，结束时间和工作效率，r表示一头奶牛工作后要r时间后换下一个奶牛。问最大工作效率。

对所有奶牛的开始时间排序，由前向后dp。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
struct Node{
	int start;
	int end;
	int efficitive;
}A[1010];
int dp[1010];
bool cmp(Node a,Node b)
{
	return a.start<b.start;
}
int Max(int a,int b)
{
	return a>b?a:b;
}
int main()
{
	int N,M,R,i,j;
	while(scanf("%d%d%d",&N,&M,&R)!=EOF)
	{
		for(i=0;i<M;++i)
		{
			scanf("%d%d%d",&A[i].start,&A[i].end,&A[i].efficitive);
			A[i].end+=R;
		}
		stable_sort(A,A+M,cmp);
		int count;
		count=dp[0]=A[0].efficitive;
		for(i=1;i<M;++i)
		{
			dp[i]=A[i].efficitive;
			for(j=i-1;j>=0;--j)
			{
				if(A[i].start-A[j].end>=0)
				{
					dp[i]=Max(dp[i],dp[j]+A[i].efficitive);
				}
			}
			count=Max(count,dp[i]);
		}
		printf("%d\n",count);
	}
	return 0;
}
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

eg6.Monkey and Banana HDU - 1069

https://cn.vjudge.net/problem/HDU-1069
A group of researchers are designing an experiment to test the IQ of a monkey. They will hang a banana at the roof of a building, and at the mean time, provide the monkey with some blocks. If the monkey is clever enough, it shall be able to reach the banana by placing one block on the top another to build a tower and climb up to get its favorite food.

The researchers have n types of blocks, and an unlimited supply of blocks of each type. Each type-i block was a rectangular solid with linear dimensions (xi, yi, zi). A block could be reoriented so that any two of its three dimensions determined the dimensions of the base and the other dimension was the height.

They want to make sure that the tallest tower possible by stacking blocks can reach the roof. The problem is that, in building a tower, one block could only be placed on top of another block as long as the two base dimensions of the upper block were both strictly smaller than the corresponding base dimensions of the lower block because there has to be some space for the monkey to step on. This meant, for example, that blocks oriented to have equal-sized bases couldn’t be stacked.

Your job is to write a program that determines the height of the tallest tower the monkey can build with a given set of blocks.
Input
The input file will contain one or more test cases. The first line of each test case contains an integer n,
representing the number of different blocks in the following data set. The maximum value for n is 30.
Each of the next n lines contains three integers representing the values xi, yi and zi.
Input is terminated by a value of zero (0) for n.
Output
For each test case, print one line containing the case number (they are numbered sequentially starting from 1) and the height of the tallest possible tower in the format “Case case: maximum height = height”.
Sample Input
1
10 20 30
2
6 8 10
5 5 5
7
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
6 6 6
7 7 7
5
31 41 59
26 53 58
97 93 23
84 62 64
33 83 27
0
Sample Output
Case 1: maximum height = 40
Case 2: maximum height = 21
Case 3: maximum height = 28
Case 4: maximum height = 342

题意：给出不同种长方形，求可摞的最高高度，要求上面的长方体的长和宽大于下面的长方体。

dp[i]表示被摞在第i个长方体的最高高度。
每一个正方形有六种摆法，共有k种状态，对宽度由大到小排序。
如果满足条件：dp[i]=dp[j]+a[i].h。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[200];
struct aaa{
	int l;
	int w;
	int h;
};
int cmp(aaa x,aaa y){
	if(x.l==y.l)return x.w>y.w;
	else return x.l>y.l;
}
int n,x,y,z;
int main(){
	int cas=1;
	while(~scanf("%d",&n)){
		if(n==0)break;
		int k=0;
		aaa ch[200];
		for(int i=0;i<n;i++){
			scanf("%d%d%d",&x,&y,&z);
			ch[k].l=x,ch[k].w=y,ch[k].h=z;k++;
			ch[k].h=x,ch[k].l=y,ch[k].w=z;k++;
			ch[k].w=x,ch[k].h=y,ch[k].l=z;k++;
			ch[k].l=x,ch[k].h=y,ch[k].w=z;k++;
			ch[k].h=x,ch[k].w=y,ch[k].l=z;k++;
			ch[k].w=x,ch[k].l=y,ch[k].h=z;k++;   
		}
		sort(ch,ch+k,cmp);
		for(int i=0;i<k;i++)dp[i]=ch[i].h;
		for(int i=k-2;i>=0;i--){
			for(int j=i;j<k;j++){
				if(ch[i].l>ch[j].l&&ch[i].w>ch[j].w){
					if(dp[i]<dp[j]+ch[i].h ){
						dp[i]=dp[j]+ch[i].h;
					}
				}
			}
		}
		int sum=dp[0];
		for(int i=0;i<k;i++){
			sum=max(sum,dp[i]);
		}
		printf("Case %d: maximum height = ",cas++);
		cout<<sum<<endl;
	}
	return 0;
} 
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

eg7.传纸条

p1006
题目描述
小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个mm行nn列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标(1,1(1,1)，小轩坐在矩阵的右下角，坐标(m,n)(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。

在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙。反之亦然。

还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用00表示），可以用一个0-1000−100的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这22条路径上同学的好心程度之和最大。现在，请你帮助小渊和小轩找到这样的22条路径。

输入格式
输入文件，第一行有22个用空格隔开的整数mm和nn，表示班里有mm行nn列。

接下来的mm行是一个m \times nm×n的矩阵，矩阵中第ii行jj列的整数表示坐在第ii行jj列的学生的好心程度。每行的nn个整数之间用空格隔开。

输出格式
输出文件共一行，包含一个整数，表示来回22条路上参与传递纸条的学生的好心程度之和的最大值。

输入输出样例
输入 #1
3 3
0 3 9
2 8 5
5 7 0
输出 #1
34

可以转化为两条不同的从左上角传到右下角的路线，所以终点为（m-1,n),(m,n-1).
设f[m-1][n][m][n-1]为答案，对于每一步，都有2* 2=4种情况，看当前点是由哪种情况转移来的。

#include<bits/stdc++.h>
using namespace std;
int m,n;
int a[51][51];
int f[52][52][52][52];
int main(){
	cin>>m>>n;
	for(int i=1;i<=m;i++)
	for(int j=1;j<=n;j++){
		cin>>a[i][j];
	}
	for(int i=1;i<=m;i++)
	for(int k=1;k<=n;k++)
	for(int j=1;j<=m;j++)
	for(int g=k+1;g<=n;g++){//两种路线不能重合
		
		f[i][k][j][g]=max(f[i-1][k][j-1][g],max(f[i][k-1][j-1][g],max(f[i-1][k][j][g-1],f[i][k-1][j][g-1])))+a[i][k]+a[j][g];
		
	}
	cout<<f[m][n-1][m-1][n];
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

eg8.最长对角线

p1736
题目描述
回到家中的猫猫把三桶鱼全部转移到了她那长方形大池子中，然后开始思考：到底要以何种方法吃鱼呢（猫猫就是这么可爱，吃鱼也要想好吃法 ^_*）。她发现，把大池子视为01矩阵（0表示对应位置无鱼，1表示对应位置有鱼）有助于决定吃鱼策略。

在代表池子的01矩阵中，有很多的正方形子矩阵，如果某个正方形子矩阵的某条对角线上都有鱼，且此正方形子矩阵的其他地方无鱼，猫猫就可以从这个正方形子矩阵“对角线的一端”下口，只一吸，就能把对角线上的那一队鲜鱼吸入口中。

猫猫是个贪婪的家伙，所以她想一口吃掉尽量多的鱼。请你帮猫猫计算一下，她一口下去，最多可以吃掉多少条鱼？

输入格式
有多组输入数据，每组数据：

第一行有两个整数n和m（n,m≥1），描述池塘规模。接下来的n行，每行有m个数字（非“0”即“1”）。每两个数字之间用空格隔开。

对于30%的数据，有n,m≤100

对于60%的数据，有n,m≤1000

对于100%的数据，有n,m≤2500

输出格式
只有一个整数——猫猫一口下去可以吃掉的鱼的数量，占一行，行末有回车。

输入输出样例
输入 #1
4 6
0 1 0 1 0 0
0 0 1 0 1 0
1 1 0 0 0 1
0 1 1 0 1 0
输出 #1
3

对于一个矩形，对角线有左上到右下、右上到左下两种，s1[i][j]表示（i,j)点水平线上向右数有多少个连续的0，s2[i][j]表示（i,j)竖直线上向上数连续0的个数。
f[i][j]表示以（i,j)为最低点最长对角线长度。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m;
int a[2505][2505];
int f[2505][2505],s1[2505][2505],s2[2505][2505];
int main(){
	scanf("%d%d",&n,&m);
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%d",&a[i][j]);
			if(a[i][j]){
				f[i][j]=min(f[i-1][j-1],min(s1[i][j-1],s2[i-1][j]))+1;
				ans=max(ans,f[i][j]);
			}
			else{
				s1[i][j]=s1[i][j-1]+1;
				s2[i][j]=s2[i-1][j]+1;
			}
		}
	}
	memset(f,0,sizeof(f));
	memset(s1,0,sizeof(s1));
	memset(s2,0,sizeof(s2));
	for(int i=n;i>=1;i--){
		for(int j=1;j<=m;j++){
			if(a[i][j]){
				f[i][j]=min(f[i+1][j-1],min(s1[i][j-1],s2[i+1][j]))+1;
				ans=max(ans,f[i][j]); 
			}
			else{
				s1[i][j]=s1[i][j-1]+1;
				s2[i][j]=s2[i+1][j]+1;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}
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

eg9.乌龟棋

p1541
题目描述
乌龟棋的棋盘是一行NN个格子，每个格子上一个分数（非负整数）。棋盘第1格是唯一的起点，第NN格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。

乌龟棋中MM张爬行卡片，分成4种不同的类型（MM张卡片中不一定包含所有44种类型的卡片，见样例），每种类型的卡片上分别标有1,2,3,41,2,3,4四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。

游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。

很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡片使用顺序使得最终游戏得分最多。

现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到多少分吗？

输入格式
每行中两个数之间用一个空格隔开。

第11行22个正整数N,MN,M，分别表示棋盘格子数和爬行卡片数。

第22行NN个非负整数，a_1,a_2,…,a_Na 表示棋盘第ii个格子上的分数。

第33行MM个整数，b_1,b_2,…,b_Mb 表示M张爬行卡片上的数字。

输入数据保证到达终点时刚好用光MM张爬行卡片。

输出格式
11个整数，表示小明最多能得到的分数。

输入输出样例
输入 #1
9 5
6 10 14 2 8 8 18 5 17
1 3 1 2 1
输出 #1
73

因为只有4种步数，且出牌规律不定，可以先统计不同步数的牌数，t表示第几个格。
第t个格有四种方法可以走过来，分别比较四种方法的最大值。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[355],b[355];
int n,m;
int dp[41][41][41][41];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	memset(b,0,sizeof(b));
	int x;
	for(int i=1;i<=m;i++){
		scanf("%d",&x);
		b[x]++;
	}
	dp[0][0][0][0]=a[1];
	for(int i=0;i<=b[1];i++){
		for(int j=0;j<=b[2];j++){
			for(int k=0;k<=b[3];k++){
				for(int l=0;l<=b[4];l++){
					int t=a[i+j*2+k*3+l*4+1];
					if(i)dp[i][j][k][l]=max(dp[i-1][j][k][l]+t,dp[i][j][k][l]);
					if(j)dp[i][j][k][l]=max(dp[i][j-1][k][l]+t,dp[i][j][k][l]);
					if(k)dp[i][j][k][l]=max(dp[i][j][k-1][l]+t,dp[i][j][k][l]);
					if(l)dp[i][j][k][l]=max(dp[i][j][k][l-1]+t,dp[i][j][k][l]);
				}
			}
		}
	}
	cout<<dp[b[1]][b[2]][b[3]][b[4]]<<endl;
	return 0;
}
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