题目大意：现有n行数，以金字塔的形式排列，即第一行一个数字，第二行2个数字，依次类推，现在需要找一条从第一层到第n层的路线，使得该路线上的所有点的权值和最大
思路：根据分析可以得出状态转移方程：dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])，dp[i][j]表示以第i行第j个位置作为终点的的线路中的最大权值。
#include <iostream> using namespace std; const int N = 360; int s[N][N]; int dp[N][N]; int main () { int n;cin >> n; for(int i=1;i <= n;i++) for(int j=1;j <= i;j++) cin >> s[i][j]; for(int i=n;i ;i--) { for(int j=1;j <= i;j++)//从下网上依次找到最大的 { dp[i][j] = s[i][j] + max(dp[i+1][j],dp[i+1][j+1]); } } cout<< dp[1][1]<<endl; return 0; }
题目大意：求把一个整数分解为2的幂的和共有几种方案
6=1+1+1+1+1+1
6=1+1+1+1+2
6=1+1+2+2
6=1+1+4
6=2+2+2
6=2+4
思路1：
如果i为奇数，肯定有一个1，把f[i-1]的每一种情况加一个1就得到fi,所以f[i]=f[i-1]
如果i为偶数，如果有1，至少有两个，则f[i-2]的每一种情况加两个1，就得到i，
如果没有1，则把分解式中的每一项除2，则得到f[i/2] （比如 4 = 2+2 ，4 = 4 除2后就变成 2 = 1 + 1 ， 2 = 2）
所以f[i]=f[i-2]+f[i/2]
#include <iostream> #include <cstdio> using namespace std; const int mod = 1e9 ; const int maxn = 1000000 + 5; typedef long long LL; LL dp[maxn]; int main() { int n; cin >> n; dp[0] = 1,dp[1] = 1; for(int i=2;i<=n;i++) { if(i & 1)//奇数 dp[i] = dp[i-1]; else//偶数 { dp[i] = dp[i-2] + dp[i/2],dp[i] %= mod; } } cout<< dp[n] <<endl; return 0; }
思路2：
题目分析： d[i][v] 表示前i物品之和为v的最多数量, 有状态转移方程 d[i][v] = sum( d[i-1][v-k*c[i]] | 0 < k*c[i] <=v)
利用完全背包O(vn)优化的思想， 这里思想是相同的，则d[v] += d[v-c[i]]
#include <iostream> #include <cstdio> using namespace std; const int mod = 1e9; const int maxn = 1e6 + 5; const int INF = 0x3f3f3f3f; typedef long long LL; int s[20]; LL dp[maxn]; int main() { int n; scanf("%d",&n); s[0] = 1; for(int i=1;i<20;i++) s[i] = s[i-1]*2; //打表记录 2的0-20次方 dp[0] = 1; for (int i =0;i < 20; i++){ if(s[i] > n) break; for(int j=s[i];j <= n ;j++){ dp[j] += dp[ j-s[i] ] ; if(dp[j] > mod ) dp[j] %= mod; } } printf("%lld",dp[n]); return 0; }
题意：有两棵苹果树，标号分别为1,2。每分钟有其中的一棵树会掉下一个苹果，奶牛一分钟只能在其中一棵树下接到苹果，但她不知道下一分钟会是那棵树掉下苹果，所以她就要在两棵树下来回跑。但她只会在树下跑W次。问你在T分钟内，奶牛bessie最多能接到多少苹果。
思路:一道简单的DP。
先给出状态转移方程：dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+count。这里的dp[i][j]代表在第i分钟移动j次最多能接到的苹果数。
在第i分钟奶牛到某棵树下有两种状态：
1.从另一棵树走过来(dp[i-1][j-1])
2.本来就呆在这棵树下(dp[i-1][j])。所以在第i分钟时能接到的最大苹果数就是dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+count。
这里count的值可以这样计算：如果j为偶数说明她移动了j次又回到了第一棵树下，则count=a[i]==1?1:0;即count=2-a[i]。若j为奇数说明她移动了j次后到了第二棵树下，则count=a[i]==2?1:0（即count=a[i]-1)。
#include <iostream> #include <cstdio> using namespace std; const int mod = 1e9 + 7; const int maxn = 1000 + 5; const int INF = 0x3f3f3f3f; typedef long long LL; int s[maxn]; int dp[maxn][40];//p[i][j]代表第i棵树 最多j次走 最大能吃到的Apple int solve (int t,int w) { int count; for(int i=0;i <= w;i++) dp[0][i] = 0;//初始化 for(int i =1;i <= t;i++)//一共最多w次 { dp[i][0] = dp[i-1][0] + 2-s[i]; //如果一次没动过 只要s[i] = 1 就 +1 for(int j=0;j <= w;j++) { if(j % 2) //j是奇数 此时在第2颗树上 count =s[i] -1 ; //如果s[i] =2 说明有1次 else //j是偶数 此时在第1颗树上 count = 2-s[i]; dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]) + count; } } count = 0; for(int i=1;i <= t;i++){ for(int j=0;j <= w ;j++){ if(dp[i][j] > count ) count = dp[i][j]; } } return count; } int main() { int t,w; scanf("%d %d",&t,&w); for(int i=1;i <= t;i++) { cin >> s[i]; } cout<< solve(t,w)<<endl; return 0; }
//其实第三题的 count不需要比较 因 //为递推的时候dp = max(dp[i-1][j] ,dp[i][j]) 了 就是现在的状态记录的已经是最优解 count = 0; for(int i=1;i <= t;i++){ for(int j=0;j <= w ;j++){ if(dp[i][j] > count ) count = dp[i][j]; } } return count; //所以这段可以 直接修改为 return dp[t][w];
题意：
在一个农场里，在长度为N个时间可以挤奶，但只能挤M次，且每挤一次就要休息t分钟；
接下来给m组数据表示挤奶的时间与奶量求最大挤奶量
思路：
每次 结束时间 += 休息的时间，接着按照 开始时间 排序
接着 状态转移方程 dp[i] = max(dp[i] , dp[j] + dp[i].cost) ( j > i && s[j].start >= s[i].end )
#include <iostream> #include <algorithm> using namespace std; struct P{ int left,ri,cost; bool operator < (const P & other)const { return (left < other.left||(left == other.left) &&ri < other.ri ); } }s[1010]; int dp[1010]; int main () { int n,m,t; cin >>n>>m>>t; for(int i=1;i<= m;i++){ cin >> s[i].left>> s[i].ri >> s[i].cost; s[i].ri += t; } sort(s+1,s+1+m); for(int i=m; i ;i--) { dp[i] = s[i].cost; for(int j=i+1 ; j <= m;j++) { if(s[j].left >= s[i].ri) dp[i] = max(dp[i], dp[j] + s[i].cost);//状态转移方程 } } int count = 0; for(int i=1;i <= m;i++) count = max(count ,dp[i]); cout<< count<<endl; return 0; }
poj（3280）Cheapest Palindrome（区间dp）
题意：
给出一个由m中字母组成的长度为n的串，给出m种字母添加和删除花费的代价，求让给出的串变成回文串的代价。
思路：
我们知道求添加最少的字母让其回文是经典dp问题，转化成LCS求解。这个是一个很明显的区间dp
我们定义dp [ i ] [ j ] 为区间 i 到 j 变成回文的最小代价。
那么对于dp [ i ] [ j ]有三种情况
首先：对于一个串如果s[ i ]==s[ j ]，那么dp [ i ] [ j ]=dp [ i+1 ] [ j-1 ]
其次：如果区间 [ i+1, j ]已经维护成回文串，那么dp [ i ] [ j ]=dp [ i+1 ] [ j ]+min（add[ i ]，del[ i ]）；
最后，如果区间 [ i, j-1 ]已经维护成回文串，那么dp [ i ] [ j ]=dp [ i ] [ j-1 ]+min（add[ j ]，del[ j ]）；
#include <stdio.h> #include <string.h> #include <cmath> #include <iostream> using namespace std; int dp[2005][2005]; int cost[300]; int n,m; char s[2005]; int main () { while (cin >> m >> n)//m表示可以增删的字符的个数 n表示字符串长度 { memset(dp,0,sizeof(dp)); cin >> s+1 ; for(int i=0;i < m;i++){ char ch; int x ,y; cin >> ch >>x >> y; cost[ ch ] = min(x,y); }//存储数据 for(int i=n; i ;i--) { for(int j=i+1;j <= n;j++) { if( s[i] == s[j] ) dp[i][j] = dp[i+1][j-1];//长度收缩一下 else dp[i][j] = min(dp[i+1][j] + cost[ s[i] ],dp[i][j-1] + cost[ s[j] ]); } } cout<< dp[1][n] <<endl; } return 0; }
题意：
给出n个coins 的价值 和 数量 求出 可以构造出 小于m的数量
思路：
基本就是挑战的原题了 用的多重部分和 看到网上说的就是多重背包
加深了一点点儿的想法把
dp[i][j] := 用前i种硬币凑成j时第i种硬币最多能剩余多少个（-1表示配不出来） 如果dp[i - 1][j] >= 0(前i-1个数可以凑出j，那么第i个数根本用不着)直接为C[i] dp[i][j] = 如果j < A[i]或者dp[i][j - a[i]] <=0 (面额太大或者在配更小的数的时候就用光了）-1 其他（将第i个数用掉一个） dp[i][j-a[i]] - 1
#include <iostream> #include <string.h> #include <algorithm> using namespace std; const int maxn = 100010; int price[105] , num[105]; int dp[maxn]; //dp[i][j]表示在用前i种coins 用的第i种硬币还剩余的情况 int n,m; int main () { while (cin >> n >> m && n+m){ for(int i=1;i <= n;i++ ) cin >> price[i]; for(int i=1;i <= n;i++) cin >>num[i]; memset(dp,-1,sizeof(dp)); dp[0] = 0; for(int i=1;i <= n;i++) { for(int j=0;j <= m;j++) { if(dp[ j ] >= 0)//前面 i-1已经算出来了 dp[j] = num[i]; else if(dp[ j-price[i] ] <= 0 || j < price[i] ) dp[j] = -1; else dp[j] = dp[j-price[i] ] -1; } } int ans = 0; for(int i=1;i <= m;i++) if( dp[i] >= 0 ) ans++; cout<< ans <<endl; } return 0; }
http://www.hankcs.com/program/cpp/poj-1742-coins.html
背包加深一下理解 就是 如果dp优化成一维的 如果需要更新自己当前行的值 就 j从0到m 如果不需要更新自己当前行的值 j就从m到0