蓝桥杯专题之动态规划

2020年：矩阵

2021年：砝码称重

3道经典线性DP问题（可能会考到类似的题哦）：

        摆花

        合唱队形

        导d拦截

1道经典区间DP问题

        石子合并

把 1 ∼ 2020 放在 2 × 1010 的矩阵里。

要求同一行中右边的比左边大，同一列中下边的比上边的大。

一共有多少种方案？

答案很大，你只需要给出方案数除以 2020 的余数即可。

这道题和“杨老师的照相排列”是同类型的题（“杨老师的照相排列”这道题属于经典题型，建议记住！！）

既然说到了，我们就来总结一下这一类的模板：

将1~N的这N个数放在k行中，每一行的数从左到右依次递增，每一列的数从前到后依次递增，问有多少种排法？

这里的k我们假设为5

我们在排的时候的前提就是：前一排的数一定要大于后一排的数 

s[0]~s[4]分别是第一排~第五排需要站的人数

f[a][b][c][d][e] 表示第一排a人，第二排b人，第三排c人，第四排d人，第五排e人时的方案数

f[0][0][0][0][0] = 1;
for (int a = 0; a <= s[0]; a ++ )
    for (int b = 0; b <= s[1]; b ++ )
    	for (int c = 0; c <= s[2]; c ++ )
        	for (int d = 0; d <= s[3]; d ++ )
                for (int e = 0; e <= s[4]; e ++ ){
                    LL &x = f[a][b][c][d][e];
                    if (a && a - 1 >= b){
						x += f[a - 1][b][c][d][e];//第一排人数必须大于第二排
					} 
                    if (b && b - 1 >= c){
						x += f[a][b - 1][c][d][e];//第二排人数必须大于第三排 
					} 
                    if (c && c - 1 >= d){
						x += f[a][b][c - 1][d][e];//第三排人数必须大于第四排 
					} 
                    if (d && d - 1 >= e){
						x += f[a][b][c][d - 1][e];//第四排人数必须大于第五排 
					} 
                    if (e){
						x += f[a][b][c][d][e - 1];
					} 
                }
cout << dp[s[0]][s[1]][s[2]][s[3]][s[4]];

然后我们开始写这道题的代码把！ 

#include
using namespace std;
int dp[1015][1015];
int main(){
	dp[0][0] = 1;
	for(int i = 0;i <= 1010;i++){
		for(int j = 0;j <= 1010;j++){
			if(i && i-1 >= j){
				dp[i][j] += dp[i-1][j]%2020;
			}
			if(j){
				dp[i][j] += dp[i][j-1]%2020;
			}
		}
	}
	cout << dp[1010][1010];
	return 0;
}

题目描述

你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W1, W2, · · · , WN。

请你计算一共可以称出多少种不同的重量？
注意砝码可以放在天平两边。

输入

输入的第一行包含一个整数 N。

第二行包含 N 个整数：W1, W2, W3, · · · , WN。

输出

输出一个整数代表答案。

样例输入

3
1 4 6
样例输出

10
提示

【样例说明】
能称出的 10 种重量是：1、2、3、4、5、6、7、9、10、11。

1 = 1；
2 = 6-4 (天平一边放 6，另一边放 4)；
3 = 4-1；
4 = 4；
5 = 6-1；
6 = 6；
7 = 1 + 6；
9 = 4 + 6 -1；
10 = 4 + 6；
11 = 1 + 4 + 6。

【评测用例规模与约定】
对于 50% 的评测用例，1 ≤ N ≤ 15。

对于所有评测用例，1 ≤ N ≤ 100，N 个砝码总重不超过 100000。

这道题是01背包问题的变种

dp[i][j]：表示前i个砝码是否可以称出j的重量（dp[i][j]=1表示可以，dp[i][j]=0表示不可以）

我们再把i和j对应的范围确定一下：

        1<=i<=N

        -V<=j<=V（-V表示所有砝码放左边的重量和，V表示所有砝码放右边的重量和）,但是又因为数组下标不能为负值，所有我们需要加上一个偏移量V

当前砝码有三种选择，不选，选放左边，选放右边 

不放：

        dp[i][j] |= dp[i-1][j]（不放，所以上一个状态的重量应该还是j）

放左边（前提是放上后重量不小于-V）：

        dp[i][j] |= dp[i-1][j-w[i]]（放左边重量增加，所以上一个状态的重量应该是j-w[i]）

放右边（前提是放上后重量不超过V）：

        dp[i][j] |= dp[i-1][j+w[i]]（放右边重量减少，所以上一个状态的重量应该是j+w[i]）

三种状态只要有一种可以称出重量j，dp[i][j]就为true，所以状态转移之间是“或”的关系

好了，上代码：

#include
using namespace std;
const int MAX_N = 110;
const int MAX_V = 1e5+10;
int N;
int w[MAX_N];
bool dp[MAX_N][2*MAX_V];
int main(){
	cin >> N;
	int V = 0;
	for(int i = 1;i <= N;i++){
		cin >> w[i];
		V += w[i];
	}
	dp[0][V] = true;//什么都不放也是可以的，原本是dp[0][0]=true，但是不是dp数组都加了一个偏移量V，所以就是dp[0][0+V] = true;
	for(int i = 1;i <= N;i++){
		for(int j = -V;j <= V;j++){
			dp[i][j+V] |= dp[i-1][j+V];
			if(j-w[i] >= -V){
				dp[i][j+V] |= dp[i-1][j-w[i]+V];
			}
			if(j+w[i] <= V){
				dp[i][j+V] |= dp[i-1][j+w[i]+V];
			}
		}
	}
	int ans = 0;
	for(int i = 1;i <= V;i++){
		if(dp[N][i+V]){
			ans++;
		}
	} 
	cout << ans;
	return 0;
}

问题描述

　　小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共m盆。

通过调查顾客的喜好，小明列出了顾客最喜欢的n种花，从1到n标号。

为了在门口展出更多种花，规定第i种花不能超过ai盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到大的顺序依次摆列。

　　试编程计算，一共有多少种不同的摆花方案。

输入格式

　　第一行包含两个正整数n和m，中间用一个空格隔开。

　　第二行有n个整数，每两个整数之间用一个空格隔开，依次表示a1、a2、……an。

输出格式

　　输出只有一行，一个整数，表示有多少种方案。

注意：因为方案数可能很多，请输出方案数对1000007取模的结果。

样例输入

2 4
3 2

样例输出

2

输入输出样例说明

　　有2种摆花的方案，分别是(1，1，1，2)， (1，1，2，2)。

括号里的1和2表示两种花，比如第一个方案是前三个位置摆第一种花，第四个位置摆第二种花。

数据规模和约定

　　对于20%数据，有 0 　　对于50%数据，有0 　　对于100%数据，有0

这道题是完全背包问题的变种

dp[i][j]：表示前i种花共摆了j盆的方案数

属性：count

我们再把i和j对应的范围确定一下：

        1<=i<=n

        0<=j<=m

当前种花有不选，选放1盆，选放2盆，……，选放a[i]盆

不放：

        dp[i][j] = dp[i-1][j]

放1盆（前提是放1盆后，花盆总数不超过j）：

        dp[i][j] = dp[i-1][j-1]

放2盆（前提是放2盆后，花盆总数不超过j)：

        dp[i][j] = dp[i-1][i-2]

……

放a[i]盆（……）:

        d[i][j] = dp[i-1][j-a[i]]

好了，上代码：

#include
using namespace std;
int n,m;
const int N = 110,M = 110;
int a[N];
int dp[N][M];
int main(){
	cin >> n >> m;
	for(int i = 1;i <= n;i++){
		cin >> a[i];
	} 
	dp[0][0] = 1;//什么花都不摆也是一种方案 
	for(int i = 1;i <= n;i++){
		for(int j = 0;j <= m;j++){
			for(int k = 0;k <= a[i];k++){
				if(j >= k){
					dp[i][j] += dp[i-1][j-k]%1000007;
				}
			}
		}
	}
	cout << dp[n][m];
	return 0;
}

问题描述
　　N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。

　　合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足T1<…Ti+1>…>TK(1<=i<=K)。

　　你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

　　
输入格式
　　输入的第一行是一个整数N(2<=N<=100)，表示同学的总数。

第二行有N个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。

　　
输出格式
　　输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。

　　
样例输入
8
186 186 150 200 160 130 197 220

样例输出
4

这道题是一道结合最长上升子序列和最长下降子序列的题

最少需要几位同学出列其实就是让我们算最多需要几位同学在队里

以第i位同学为中心，分别求出其左侧的最长上升子序列和其右侧的最长下降子序列

两者相加再减1就是合唱队的人数

#include
#include 
using namespace std;
const int MAX_N = 110;
int N;
int h[MAX_N],l[MAX_N],r[MAX_N];
int main(){
	cin >> N;
	for(int i = 1;i <= N;i++){
		cin >> h[i];
	}
	//求最长递增子序列 
	for(int i = 1;i <= N;i++){
		l[i] = 1;
		for(int j = 1;j < i;j++){
			if(h[j] < h[i]){
				l[i] = max(l[i],l[j]+1);
			}
		} 
	}
	//求最长递减子序列 
	for(int i = N;i >= 1;i--){
		r[i] = 1;
		for(int j = N;j > i;j--){
			if(h[j] < h[i]){
				r[i] = max(r[i],r[j]+1);
			}
		}
	}
	//以第i个同学为中心，左边的人数+右边的人数-1 
	int k = 0;
	for(int i = 1;i <= N;i++){
		k = max(k,l[i]+r[i]-1);
	}
	cout << N-k;
	return 0;
}

问题描述
　　某国为了防御敌国的导d袭击，发展出一种导d拦截系统。

但是这种导d拦截系统有一个缺陷：虽然它的第一发炮d能够到达任意的高度，但是以后每一发炮d都不能高于前一发的高度。

某天，雷达捕捉到敌国的导d来袭。

由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导d。

输入导d依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导d，如果要拦截所有导d最少要配备多少套这种导d拦截系统。

输入格式
　　一行，为导d依次飞来的高度
输出格式
　　两行，分别是最多能拦截的导d数与要拦截所有导d最少要配备的系统数
样例输入
389 207 155 300 299 170 158 65
样例输出
6
2

求一套系统最多可以拦截多少导d，就是求最长不上升子序列（注意是不高于，也就是后一枚导d的高度<=前一枚导弹的高度）

求至少需要多少套系统，就是求最长递增子序列（为什么呢？我们如果仅需1套系统，那么就必须保证所有的数从左到右单调不递增，如果中间有数破坏了这个规则，就要增加一套系统，所以如果我们知道中间有多少个数破坏了这个单调不递增的规则，那么系统数不就知道了）

#include
#include
#include 
using namespace std;
const int MAX_N = 110;
int h[MAX_N],d[MAX_N],u[MAX_N];
int main(){
	string s;
	getline(cin,s);
	istringstream is(s);
	int n = 0,k = 0;
	while(is>>k){
		h[++n] = k;
	}
	for(int i = 1;i <= n;i++){
		d[i] = 1;
		u[i] = 1;
		for(int j = 1;j < i;j++){
			if(h[j] >= h[i]){
				d[i] = max(d[i],d[j]+1);
			}
			if(h[j] < h[i]){
				u[i] = max(u[i],u[j]+1);
			}
		} 
	}
	int md = 0,mu = 0;
	for(int i = 1;i <= n;i++){
		md = max(md,d[i]);
		mu = max(mu,u[i]);
	}
	cout << md <

#include
#include
using namespace std;
const long long INF = 1e9;
const int N = 1010;
int n;
long long sum[N];
long long dp[N][N];
int main(){
	cin >> n;
	for(int i = 1;i <= n;i++){
		cin >> sum[i];
		sum[i] += sum[i-1];
	}
    dp[1][1] = 0;//只有1堆石子，不需要合并，花费为0
	for(int len = 2;len <= n;len++){
		for(int i = 1;i+len-1 <= n;i++){
			int j = i+len-1;
			dp[i][j] = INF;
			for(int k = i;k < j;k++){
				dp[i][j] = min(dp[i][j],dp[i][k] + dp[k+1][j] + sum[j]-sum[i-1]);
			}
		}
	}
	cout << dp[1][n];
	return 0;
}