开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 一本通动态规划专栏 -> 正文阅读

[数据结构与算法]一本通动态规划专栏

数塔问题

【问题描述】

观察下面的数塔。写一个程序查找从最高点到底部任意位置结束的路径，使路径经过数字的和最大。
每一步可以从当前点走到左下角的点，也可以到达右下角的点。

image.png

【输入形式】

【输出形式】

【样例输入】

5
13
11 8
12 7 26
6 14 15 8
12 7 13 24 11
【样例输出】

max=86

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
# include<iostream>
# include<algorithm>
# include<cmath>
# include<cstdio>
# include<set>
# include<stack>
# include<queue> 
# include<map>
# include<string>
# include<cstring> 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int > PII; 
const int mod=1e9+7;
const int MAX=2e6+10;
const int Time=86400;
const int X=131;
const int inf=0x3f3f3f3f;
const double PI = 1e-4;
double pai = 3.14159265358979323846; 

ll n,dp[2005][2005];
ll a[2005][2005],maxn;

int main(){  
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n ;
    for(int i = 1 ; i <= n ; i++ )
     for(int j = 1 ; j <= i ; j++ )
      cin >> a[i][j];
    memset(dp,-inf,sizeof dp);
    dp[1][1] = a[1][1];
    
    for(int i = 2 ; i <= n ; i ++ )
     for(int j = 1 ; j <= i ; j ++ )
      dp[i][j] = max(dp[i - 1][j] + a[i][j] , dp[i - 1][j - 1] + a[i][j]);
      
   maxn = dp[n][1];
   for(int i = 1 ; i <= n ; i++ ) maxn = max(maxn,dp[n][i]);
   cout<<"max="<<maxn;
	return 0;
}

最长不下降序列

【问题描述】

设有由n(1<=n<=200)个不相同的整数组成的数列，记为:b(1)、b(2)、……、b(n)且b(i)<>b(j)(i<>j)，若存在i1<i2<i3< <="" p="" …="" 且有b(i1)<= ie="">
例如13，7，9，16，38，24，37，18，44，19，21，22，63，15。例中13，16，18，19，21，22，63就是一个长度为7的不下降序列，同时也有7 ，9，16，18，19，21，22，63组成的长度为8的不下降序列。

【输入形式】

第一行为n,第二行为用空格隔开的n个整数。

【输出形式】

第一行为输出最大个数max(形式见样例)；

第二行为max个整数形成的不下降序列,答案可能不唯一，输出一种就可以了，本题进行特殊评测。

【样例输入】

13 7 9 16 38 24 37 18 44 19 21 22 63 15

【样例输出】

max=8

7 9 16 18 19 21 22 63

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
# include<iostream>
# include<algorithm>
# include<cmath>
# include<cstdio>
# include<set>
# include<stack>
# include<queue> 
# include<map>
# include<string>
# include<cstring> 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int > PII; 
const int mod=1e9+7;
const int MAX=2e6+10;
const int Time=86400;
const int X=131;
const int inf=0x3f3f3f3f;
const double PI = 1e-4;
double pai = 3.14159265358979323846; 

int n , t,x , a[MAX] ,pre[MAX],bk,b[MAX],dp[MAX],ans;

int main(){  
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1 ; i <= n ; i ++ ) cin >> a[i] ,dp[i] = 1;
    ans = 1;
    
    for(int i = 1 ; i <= n ; i ++ ){
    	 for(int j = 1 ; j < i ; j++)
    	  if(a[i] >= a[j]){
    	  	  dp[i] = max(dp[i] , dp[i] = dp[j] + 1);
    	  	   pre[i] = j;
    	  
		  }
		  if(dp[i] > ans){
		  	 ans = dp[i];
		  	 bk = i;
		  }
	}
	cout<<"max="<<ans<<"\n";
	while(bk){
	   	b[++t] = a[bk];
	   	bk=pre[bk];
	}
	for(int i = t ; i >= 1 ; i -- )
	 cout<<b[i]<<" ";
	return 0;
}

导弹拦截

【问题描述】

某国为了预防敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够达到任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

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

【输入形式】

一行，输入导弹依次飞来的高度

【输出形式】

共两行，第1行为最多拦截的导弹数，第2行输出要拦截所有导弹最少要配备的系统数

【样例输入】

389 207 155 300 299 170 158 65

【样例输出】

6
2


# include<iostream>
# include<algorithm>
# include<cmath>
# include<cstdio>
# include<set>
# include<stack>
# include<queue> 
# include<map>
# include<string>
# include<cstring> 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int > PII; 
const int mod=1e9+7;
const int MAX=2e6+10;
const int Time=86400;
const int X=131;
const int inf=0x3f3f3f3f;
const double PI = 1e-4;
double pai = 3.14159265358979323846; 
int n , dp[MAX],a[MAX],len,q[MAX],p[MAX];

int main(){  
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    while(cin >> a[++n]);
    n--;
    len = 0;
    q[0] = -inf;
    for(int i = 1 ; i <= n ; i ++ ){
         int l = 0 , r = len ;
		 while(l < r){
		 	int mid = l + r + 1>> 1;
		 	if(q[mid] >= a[i]) l = mid;
		 	 else r = mid - 1;
		 }	
		 q[l + 1] = a[i];
		 len = max(len,l + 1); 
	}
	cout<<len <<"\n";
	
    len = 0;
    p[++len] = a[1]; 
      for(int i = 1 ; i <= n ; i ++){
        int k = 0;
        for(int j = 1 ; j <= len ; j ++)	
		   if(p[j] >= a[i]){
		   	  if(k == 0 ) k = j;
		   	   else if(p[k] > p[j]) k = j;
		   }
		
        if(k == 0 ){
        	 p[++len] = a[i];
		}
		else p[k] = a[i];
	}
	cout<<len;
	return 0;
}

友好城市

【问题描述】

Palmia国有一条横贯东西的大河，河有笔直的南北两岸，岸上各有位置各不相同的N个城市。北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相同。

每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市，但是由于河上雾太大，政府决定避免任意两条航道交叉，以避免事故。编程帮助政府做出一些批准和拒绝申请的决定，使得在保证任意两条航线不相交的情况下，被批准的申请尽量多。

【输入形式】

第1行，一个整数N(1≤N≤5000)，表示城市数。

第2行到第n+1行，每行两个整数，中间用1个空格隔开，分别表示南岸和北岸的一对友好城市的坐标。(0≤xi≤10000)

【输出形式】

仅一行，输出一个整数，表示政府所能批准的最多申请数。

【样例输入】

22 4

2 6

10 3

15 12

9 8

17 17

4 2

【样例输出】

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
# include<iostream>
# include<algorithm>
# include<cmath>
# include<cstdio>
# include<set>
# include<stack>
# include<queue> 
# include<map>
# include<string>
# include<cstring> 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int > PII; 
const int mod=1e9+7;
const int MAX=2e6+10;
const int Time=86400;
const int X=131;
const int inf=0x3f3f3f3f;
const double PI = 1e-4;
double pai = 3.14159265358979323846; 
int n,b[MAX],len;
struct Node{
	int x,y;
	bool operator <(const Node &p) const{
		 return x < p.x;
	}
}a[MAX];

int main(){  
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
	for(int i = 1 ; i <= n ; i ++ ) cin >> a[i].x >> a[i].y ;
	sort(a + 1,a + 1 + n);
	b[++len] = a[1].y ;
	for(int i = 2 ; i <= n ; i++ ){
		int d = upper_bound(b + 1 , b + len + 1,a[i].y) - b;
		b[d] = a[i].y ;
		if(d > len) len++;
	}
	cout<<len;
	return 0;
}

合唱队形

【问题描述】

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

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

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

【输入形式】

输入的第一行是一个整数N（2≤N≤100），表示同学的总数。第二行有n个整数，用空格分隔，第i个整数Ti（130≤Ti≤230）是第i位同学的身高（厘米）。

【输出形式】

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

【样例输入】

186 186 150 200 160 130 197 220

【样例输出】

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
# include<iostream>
# include<algorithm>
# include<cmath>
# include<cstdio>
# include<set>
# include<stack>
# include<queue> 
# include<map>
# include<string>
# include<cstring> 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int > PII; 
const int mod=1e9+7;
const int MAX=2e6+10;
const int Time=86400;
const int X=131;
const int inf=0x3f3f3f3f;
const double PI = 1e-4;
double pai = 3.14159265358979323846; 

int n , a[MAX] , dp1[MAX] , dp2[MAX],ans;


int main(){  
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1 ; i <= n ; i++) cin >> a[i];
    for(int i = 1 ; i <= n ; i++){
    	dp1[i] = 1;
    	for(int j = 1 ; j < i ; j++)
    	 if(a[i] > a[j]) dp1[i] = max(dp1[i] , dp1[j] + 1);
	}
	
	for(int i = 1 ; i <= n ; i++){
    	dp2[i] = 1;
    	for(int j = 1 ; j < i ; j++)
    	 if(a[i] < a[j]) dp2[i] = max(dp2[i] , max(dp1[j],dp2[j]) + 1);
	}
	
	ans = 0;
	for(int i = 1 ; i <= n ; i++)
	 ans = max(ans,max(dp1[i],dp2[i]));
	cout<<n - ans;
	return 0;
}

最长公共子序列

【问题描述】

一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X= { x1, x2,…, xm}，则另一序列Z= {z1, z2,…, zk}是X的子序列是指存在一个严格递增的下标序列 {i1, i2,…, ik}，使得对于所有j=1,2,…,k有 Xij=Zj。

例如，序列Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列，相应的递增下标序列为{2,3,5,7}。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。例如，若X= { A, B, C, B, D, A, B}和Y= {B, D, C, A, B, A}，则序列{B,C,A}是X和Y的一个公共子序列，序列{B,C,B,A}也是X和Y的一个公共子序列。而且，后者是X和Y的一个最长公共子序列，因为X和Y没有长度大于4的公共子序列。给定两个序列X= {x1, x2, …, xm}和Y= {y1, y2, … , yn}，要求找出X和Y的一个最长公共子序列。

【输入形式】

输入共两行。每行为一个由大写字母构成的长度不超过200的字符串，表示序列X和Y。

【输出形式】

输出第一行为一个非负整数。表示所求得的最长公共子序列的长度。若不存在公共子序列，则输出仅有一行输出一个整数0。

【样例输入】

ABCBDAB

BDCABA

【样例输出】

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
# include<iostream>
# include<algorithm>
# include<cmath>
# include<cstdio>
# include<set>
# include<stack>
# include<queue> 
# include<map>
# include<string>
# include<cstring> 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int > PII; 
const int mod=1e9+7;
const int MAX=2e6+10;
const int Time=86400;
const int X=131;
const int inf=0x3f3f3f3f;
const double PI = 1e-4;
double pai = 3.14159265358979323846; 

char a[MAX],b[MAX];
int n , m;
int dp[205][205];


int main(){  
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> a + 1 >> b + 1;
    n = strlen(a + 1);
    m = strlen(b + 1);
    for(int i = 1 ; i <= n ; i ++ ){
    	 for(int j = 1 ; j <= m ; j ++ ){
    	 	 dp[i][j] = max(dp[i-1][j] , dp[i][j - 1]  );
    	 	 if(a[i] == b[j])
    	 	  dp[i][j] = max(dp[i][j] , dp[i - 1][j - 1] + 1 );
		 }
	}
	cout<<dp[n][m];
	return 0;
}

机器分配

【问题描述】

总公司拥有高设备M台，准备分给下属的N个分公司。各分公司获得这些设备，可以为国家提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。其中M<=15,N<=10。分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数M。

【输入形式】

第1行有两个数，第1个数是分公司数N，第2个数是总设备台数M。接下来是N*M的矩阵，表明了第I个公司分配J台机器的盈利。

【输出形式】

第1行输出最大盈利值，接下来N行，每行2个数，即分公司编号和该公司获得设备台数。

【样例输入】

3 3

30 40 50

20 30 50

20 25 30

【样例输出】

1 1

2 1

3 1

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
# include<iostream>
# include<algorithm>
# include<cmath>
# include<cstdio>
# include<set>
# include<stack>
# include<queue> 
# include<map>
# include<string>
# include<cstring> 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int > PII; 
const int mod=1e9+7;
const int MAX=2e6+10;
const int Time=86400;
const int X=131;
const int inf=0x3f3f3f3f;
const double PI = 1e-4;
double pai = 3.14159265358979323846; 

int n , m,dp[2005][2005],a[2005][2005],pre[2005][2005];
void dfs(int x,int y){
	if(x == 0) return;
	dfs(x-1,y-pre[x][y]);
	cout<<x<<" "<<pre[x][y]<<"\n";
}
int main(){  
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i++ )
     for(int j = 1 ; j <= m ; j++)
      cin >> a[i][j];
    
    for(int i = 1 ; i <= n ; i++ )
     for(int j = 1 ; j <= m ; j++ )
      for(int k = 0 ; k <= j ; k ++){
      	 if(dp[i][j] <= dp[i-1][j-k] + a[i][k])
      	 {
      	 	dp[i][j] = dp[i-1][j-k] + a[i][k];
      	 	pre[i][j] = k;
		 }
	  }
	  cout<<dp[n][m]<<"\n";
	/*  for(int i = 1 ; i <= n ; i++ ){
	  	for(int j = 1 ; j <= m ; j ++)
	  	 cout<<pre[i][j]<<" ";
	  	 cout<<"\n";
	  	 
	  } */
	  dfs(n,m);
	return 0;
}

砝码称重

【问题描述】

设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重<=1000g）。

【输入形式】

a1、a2、a3、a4、a5、a6（表示1g砝码有a1个，2g砝码有a2个，…20g砝码有a6个）

【输出形式】

Total=n(n表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况)

【样例输入】

1 1 0 0 0 0
【样例输出】

Total=3

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
# include<iostream>
# include<algorithm>
# include<cmath>
# include<cstdio>
# include<set>
# include<stack>
# include<queue> 
# include<map>
# include<string>
# include<cstring> 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int > PII; 
const int mod=1e9+7;
const int MAX=2e6+10;
const int Time=86400;
const int X=131;
const int inf=0x3f3f3f3f;
const double PI = 1e-4;
double pai = 3.14159265358979323846; 

int a[6],c[6]={1,2,3,5,10,20};
int b[MAX],t,m,ans,dp[MAX];
int main(){  
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    dp[0] = 1;
    for(int i = 0 ; i < 6 ; i++){
    	 cin >> a[i];
    	 for(int j = 1 ; j <= a[i] ; j ++ )
    	  b[++t] = c[i] , m += c[i];
	}
	for(int i = 1 ; i <= t ; i++ ){
		 int v = b[i];
		 for(int j = m ; j >= v ; j-- )
		  dp[j] += dp[j - v];
	}
	for(int i = 1 ; i <= m ; i++)
	 if(dp[i]) ans++;
	cout<<"Total="<<ans;
	return 0;
}

装箱问题

【问题描述】

有一个箱子容量为v（正整数，0≤v≤20000），同时有n个物品（0<n≤30），每个物品有一个体积（正整数）。

要求从n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

【输入形式】

箱子的容量v

物品数n

接下来n行，分别表示这n个物品的体积

【输出形式】

箱子剩余空间

【样例输入】

【样例输出】

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
# include<iostream>
# include<algorithm>
# include<cmath>
# include<cstdio>
# include<set>
# include<stack>
# include<queue> 
# include<map>
# include<string>
# include<cstring> 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int > PII; 
const int mod=1e9+7;
const int MAX=2e6+10;
const int Time=86400;
const int X=131;
const int inf=0x3f3f3f3f;
const double PI = 1e-4;
double pai = 3.14159265358979323846; 

int m ,n , v,dp[MAX];


int main(){  
   std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> m >> n;
    for(int i = 1 ; i <= n ; i ++ ){
    	 cin >> v;
    	 for(int j = m ; j >= v ; j --)
    	  dp[j] = max(dp[j],dp[j - v] + v);
	}
	cout<<m-dp[m];
	return 0;
}