devbox
从前慢现在也慢
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

动态规划（DP）_auto dp = vector < vector > (rows, vector

作者：从前慢现在也慢 | 2024-03-28 10:49:31

赞

踩

auto dp = vector < vector > (rows, vector (columns));

洛谷 P.1359

输入说明 ：

3

5 （1->2) 15 (1->3)

7 (2 -> 3)

  1. #include<iostream>
  2. #include<vector>
  3. #include<climits>
  4. using namespace std;
  5.  
  6. vector<int> dp(201);
  7. int  main(){
  8. 	int n ;
  9. 	cin>>n;
  10. 	vector<vector<int>> ori(201,vector<int>(201));
  11. 	for(int i = 1; i < n;i++ ){
  12. 		for(int j = i + 1; j <= n;j++){
  13. 			cin>>ori[i][j];
  14. 		}
  15. 		dp[i] = INT_MAX;
  16. 	}
  17. 	for(int i = n - 1;i > 0;i--){
  18. 		for(int j = i + 1; j <= n;j++  ){
  19. 			dp[i] = min(dp[i] , dp[j] + ori[i][j]);
  20. 		}
  21. 	}
  22. 	cout<<dp[1];
  23. 	return 0;
  24. }

状态转移关系 ： 我们要用i把n上流的中转站从大到小跑一遍。我们先记录中转站2到中转站3的最小价钱，我们要用jj跑一遍中转站2下流的所有中转站，记录ori[i][j]+dp[j]的最小价钱,记录到dp[i]里面。

 

细节  ： 因为dp[i}是每次min来的，但dp各项初始化为0，因此我们要让除了最后一个中转站外设为INT_MAX（用头文件#include<climits>)

洛谷 P.1060

 

 01背包问题！

无优化代码

  1. for(int i=1;i<=n;i++)
  2. {
  3.     for(int c=0;c<=m;c++)
  4.     {
  5.         f[i][c]=f[i-1][c];
  6.         if(c>=w[i])
  7.         f[i][c]=max(f[i][c],f[i-1][c-w[i]]+v[i]);
  8.     }
  9. }

 一维数组优化 ：

  1. for(int i=1;i<=n;i++)
  2. {
  3.     for(int c=m;c>=0;c--)
  4.     {
  5.         if(c>=w[i])
  6.         f[c]=max(f[c],f[c-w[i]]+v[i]);
  7.     }
  8. }
  1. #include<iostream>
  2. using namespace std;
  3. int w[30],v[30],dp[30][100000];
  4. int main(){
  5. 	int m, n;//m为总价，n为数量
  6. 	cin>>m>>n;
  7. 	 for(int i = 1;i <=n;i++){
  8. 	 	cin>>v[i]>>w[i];
  9. 	 	w[i] *= v[i];//w[i]变为总收获 
  10. 	 }
  11. 	 for(int i = 1;i <= n;i++ ){
  12. 	 	for(int j = 0;j <= m;j++){
  13. 	 		dp[i][j] = dp[i - 1][j];
  14. 	 		if(j >= v[i]){
  15. 	 			dp[i][j] = max(dp[i][j] , dp[i - 1][j - v[i]] + w[i]);
  16. 			 }
  17. 		 }
  18. 	 }
  19. 	 cout<<dp[n][m];
  20. 	 return 0;
  21. }
  1. //优化版
  2. #include<iostream>
  3. using namespace std;
  4. int w[30],v[30],dp[100000];
  5. int main(){
  6. 	int m, n;//m为总价，n为数量
  7. 	cin>>m>>n;
  8. 	 for(int i = 1;i <= n;i++){
  9. 	 	cin>>v[i]>>w[i];
  10. 	 	w[i] *= v[i];//w[i]变为总收获 
  11. 	 }
  12. 	 for(int i = 1;i <= n;i++ ){
  13. 	 	for(int j = m;j >= v[i];j--){
  14. 	 			dp[j] = max(dp[j] , dp[j - v[i]] + w[i]);
  15. 			 
  16. 		 }
  17. 	 }
  18. 	 cout<<dp[m];
  19. 	 return 0;
  20. }

洛谷P.1802

与上题相似 直接上代码‘

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. using namespace std;
  5. int lose[1001],win[1001],use[1001];
  6. long long f[1001][1001];
  7. int main(){
  8.     int n,x;
  9.     cin>>n>>x;
  10.     for (int i=1;i<=n;i++)
  11.       cin>>lose[i]>>win[i]>>use[i];
  12.     for (int i=1;i<=n;i++)
  13.       for (int j=0;j<=x;j++)
  14.         if (j>=use[i]) f[i][j]=max(f[i-1][j-use[i]]+win[i],f[i-1][j]+lose[i]);
  15.  else f[i][j]=f[i-1][j]+lose[i];
  16.     cout<<f[n][x]*5;
  17.     return 0;
  18. }

 

  1. #include <cstdio>
  2. #include <iostream>
  3. using namespace std;
  4. int dp[1100];
  5. int win[1100],lose[1100],use[1100];
  6. int main()
  7. {
  8.     int n,m;
  9.     scanf("%d%d",&n,&m);
  10.     for(int i=1;i<=n;i++)
  11.      scanf("%d%d%d",lose+i,win+i,use+i);
  12.     for(int i=1;i<=n;i++)
  13.      {
  14.          for(int j=m;j>=use[i];j--)
  15.           dp[j]=max(dp[j]+lose[i],dp[j-use[i]]+win[i]);
  16.          for(int j=use[i]-1;j>=0;j--)
  17.           dp[j]+=lose[i];//其余情况不是0而要加lose[i]
  18.      }
  19.      printf("%lld",5ll*dp[m]);
  20. }

洛谷P.1049

 

看似与01背包不同，但我们可以看作它价值与容量相等（v[i] = w[i])，即与1060一致

状态转移关系 ： dp（x）为在x的最大容积下（对应1060的最大价格）最多能装下多少容积（对应1060最多价值），最后将m - dp（m）即为最小剩余容量 。。

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. int a[31],dp[20001];
  5.  
  6. int main(){
  7. 	int m , n;
  8. 	cin>>m>>n;
  9. 	for(int i = 1;i <= n;i++){
  10. 		cin>>a[i];
  11. 	}
  12. 	for(int i = 1;i <=n;i++){
  13. 		for(int j = m; j >= a[i];j--){
  14. 			dp[j] = max(dp[j] , dp[j -a[i]] + a[i]);  
  15. 		}
  16. 	}
  17. 	cout<<m - dp[m];
  18. 	return 0;
  19. }

 来题几何

LeetCode.221

 

 设dp（i，j）为以（i，j）为右下角的正方形边长的最大值

边界情况 ：i = 0或 j = 0并且matrix[i][j]==1时dp[i][j]为1（无法向左上角延申）

动态转移关系 ：dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;（取决于左边，坐上，上面）最小的dp（画图理解，这种题主要背）

  1.  
  2. class Solution {
  3. public:
  4.     int maximalSquare(vector<vector<char>>& matrix) {
  5.         int maxSide = 0;
  6.         int rows = matrix.size(), columns = matrix[0].size();
  7.         vector<vector<int>> dp(rows, vector<int>(columns));
  8.         for (int i = 0; i < rows; i++) {
  9.             for (int j = 0; j < columns; j++) {
  10.                 if (matrix[i][j] == '1') {
  11.                     if (i == 0 || j == 0) {
  12.                         dp[i][j] = 1;
  13.                     } else {
  14.                         dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
  15.                     }
  16.                     maxSide = max(maxSide, dp[i][j]);
  17.                 }
  18.             }
  19.         }
  20.         int maxSquare = maxSide * maxSide;
  21.         return maxSquare;
  22.     }
  23. };

LeetCode : 118

弄成二维数组看更直观 ：

1 

1   1

1    2   1

1    3   3   1

1    4   6    4   1

很容易看出边界情况 ：dp[m][0] = dp[m][m] = 1，

状态转移关系 ： dp[m][n] = dp[m - 1][n - 1] + dp[m - 1][n]，&&n > 0&&n < m

  1. class Solution {
  2. public:
  3.     vector<vector<int>> generate(int numRows) {
  4.         vector<vector<int>> dp(numRows);
  5.         for(int i = 0; i < numRows;i++ ){
  6.             dp[i].resize(i + 1);//每行变成i + 1列
  7.             dp[i][0] = 1;
  8.             dp[i][i] = 1;
  9.             for(int j = 1;j < i;j++){
  10.                 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
  11.             }
  12.         }
  13.         return dp;
  14.     }
  15. };

LeetCode : 119

 水题放松下，和118一致

  1. class Solution {
  2. public:
  3.     vector<int> getRow(int rowIndex) {
  4.         vector<vector<int>> dp(rowIndex + 1);
  5.         for(int i = 0; i < rowIndex + 1;i++ ){
  6.             dp[i].resize(i + 1);//每行变成i + 1列
  7.             dp[i][0] = 1;
  8.             dp[i][i] = 1;
  9.             for(int j = 1;j < i;j++){
  10.                 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
  11.             }
  12.         }
  13.         return dp[rowIndex];
  14.     }
  15. };

洛谷P.1757

 重点 ：他的物品大致可分为 k 组，每组中的物品相互冲突（分组背包问题）

思路 ：不同于普通01背包，第一层for循环是以小组为元素，第二层对于一个dp[j]第三层for循环要遍历一组的所有元素，以便每组中物品不冲突

  1. #include<iostream>
  2. using namespace std;
  3. int v[1001],w[1001],dp[1001],level[1001],g[1001][1001];
  4. int main(){
  5. 	int m , n , x , t;
  6. 	cin>>m>>n;
  7. 	for(int i = 1; i <= n;i++){
  8. 		cin>>v[i]>>w[i]>>x;
  9. 		t = max(t , x);
  10. 		level[x]++;
  11. 		g[x][level[x]] = i;//存储每组第几个元素的值 
  12. 	}
  13. 	for(int i = 1;i <= t; i++){//对于每个小组 
  14. 		for(int j = m ;j >=0;j--){
  15. 			for(int k = 1;k <=level[i];k++){//一组的所有元素 
  16. 				if(j >= v[g[i][k]]){
  17. 					dp[j] = max(dp[j] , dp[j - v[g[i][k]]] + w[g[i][k]]); //不让组内元素互动
  18. 				}
  19. 			}
  20. 		}
  21. 	}
  22. 	cout<<dp[m];
  23. 	return 0;
  24. }

LeetCode.509

  1. class Solution {
  2. public:
  3.     int fib(int n) {
  4.         if(n == 0) return 0;
  5.         if(n == 1) return 1;//特殊情况
  6.         int begin = 0, end = 1 , res ;
  7.         for(int i =  2;i <= n;i++){
  8.             res = begin + end;
  9.             begin = end;
  10.             end = res;//依次后移
  11.         }
  12.         return res;
  13.     }
  14. };

洛谷 P.1507

 太过简单，不做阐释

  1. #include<iostream>
  2. using namespace std;
  3. int a[401],b[401],c[501];
  4. int dp[401][401];
  5.  
  6. int main(){
  7. 	int v,m,n;
  8. 	cin>>v>>m>>n;
  9. 	for(int i = 1;i <= n;i++){
  10. 		cin>>a[i]>>b[i]>>c[i];
  11. 	} 
  12. 	for(int i = 1;i <= n;i++){
  13. 		for(int j = v;j >= a[i];j--){
  14. 			for(int k = m;k >= b[i];k--){
  15. 				dp[j][k] = max(dp[j][k] , dp[j - a[i]][k - b[i]] + c[i]);
  16. 			}
  17. 		}
  18. 	}
  19. 	cout<<dp[v][m];
  20. 	return 0;
  21. }

洛谷 P.2858

 题目特色 ： 入口有两个并且物品价值随着每次选择改变

用二维数组dp[left][right]表示从left 到right获得的最多钱

边界情况 ： dp[i][i] = s[i] * m(只剩一份零食肯定是在最后一天)

  1. #include<iostream>
  2. using namespace std;
  3. int s[2001],dp[2001][2001];
  4.  
  5. int main(){
  6. 	int m ;
  7. 	cin>>m;
  8. 	for(int i = 1; i <= m;i++ ){
  9. 		cin>>s[i];
  10. 	}
  11. 	for(int i = 1;i <= m;i++){
  12. 		dp[i][i] = m * s[i];
  13. 	}
  14. 	for(int i = 1;i <= m;i++){
  15. 		for(int left = 1;left <= m;left++){
  16. 			int right = left + i;
  17. 			if(right > m) break;
  18. 			dp[left][right] = max(dp[left + 1][right] + s[left] * (m - i),dp[left][right - 1] + s[right] * (m - i));
  19. 		}
  20. 	}
  21. 	cout<<dp[1][m];
  22. 	return 0;
  23. }

洛谷 P .1091

 

 思路 ： 找到一个数据点让它左边的递增元素数量与它右边的递减元素数量最多

  1. #include<iostream>
  2. using namespace std;
  3. int a[105],b[105],c[105];
  4.  
  5. int main(){
  6. 	int n;
  7. 	cin>>n;
  8. 	for(int i = 1;i <= n;i++){
  9. 		cin>>a[i];
  10. 	}
  11. 	for(int i = 1;i <= n;i++){//细节是从第一个数开始而第二层超出第一个数以便让i = =1时候b[i] = 1 
  12. 		for(int j = 0;j < i;j++){
  13. 			if(a[i] > a[j])
  14. 			b[i] = max(b[i],b[j] + 1);//b[i]记录i左边有几个从低到高的数 （包括自己） 
  15. 		}
  16. 	}
  17. 	for(int i = n; i>= 0;i--){
  18. 		for(int j = n + 1;j > i;j--){
  19. 			if(a[i] > a[j] ){
  20. 				c[i] = max(c[i],c[j] + 1);//c[i]记录i右边有几个从高到低的数 (包括自己） 
  21. 			}
  22. 		}
  23. 	}
  24. 	int res = 0;
  25. 	for(int i = 1;i <= n;i++){
  26. 		res = max(res,b[i] + c[i] - 1);	
  27. 	} 
  28. 	cout<< n - res;
  29. 	return 0; 
  30. }

洛谷 P.1077

 边界情况 ：dp[0] = 1(摆0盆花有1种方案)

  1. #include<iostream>
  2. using namespace std;
  3. const int mod = 1000007;
  4. int a[105],dp[105];
  5.  
  6. int main(){
  7. 	int m,n;
  8. 	cin>>m>>n;
  9. 	for(int i = 1 ; i <= m;i++){
  10. 		cin>>a[i];
  11. 	}
  12. 	dp[0] = 1;
  13. 	for(int i = 1; i <= m;i++){//枚举每个品种 
  14. 		for(int j = n;j >= 1;j--){
  15. 			for(int k = 1; k <= a[i] && k <= j;k++){//相同品种的所有花 
  16. 				dp[j] = (dp[j] + dp[j - k]) % mod;
  17. 			}
  18. 		}
  19. 	}
  20. 	cout<<dp[n];
  21. 	return 0;
  22. }

PTA . 1020 - 月饼

2022.3.6

 特点 ： 销售时允许取出一部分库存

意味着可以选择一点数据而非全选，解决方法 ：结构体

  1. //N 表示月饼的种类数
  2. //D 表示市场最大需求量
  3. //每种月饼的库存量 每种月饼的总售价
  4. //贪心问题
  5. #include<bits/stdc++.h>
  6. using namespace std;
  7. struct item{
  8. 	double cap;//容量 
  9. 	double price;//单价 
  10. }moon[1001];
  11.  
  12. bool cmp(item a,item b){
  13. 	return a.price > b.price; 
  14. }
  15.  
  16. int main(){
  17. 	int n,d;
  18. 	double res = 0.0;
  19. 	cin>>n>>d;
  20. 	for(int i = 1; i <= n;i++){
  21. 		cin>>moon[i].cap;
  22. 	}
  23. 	for(int i = 1;i <= n;i++){
  24. 		cin>>moon[i].price;
  25. 		moon[i].price /= moon[i].cap;//转化为单价
  26. 	}
  27. 	sort(moon + 1,moon + n + 1,cmp);
  28. 	for(int i = 1; i <= n;i++){
  29. 		if(d <= moon[i].cap){//供大于求
  30. 			res += moon[i].price * d;
  31. 			break;
  32. 		}
  33. 		else{//求大于供
  34. 			res += moon[i].price * moon[i].cap;
  35. 			d -= moon[i].cap;
  36. 		}
  37. 	}
  38. 	printf("%.2f",res);
  39. 	return 0;
  40. }

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/329673?site
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号