求一個數列中取m個不相交子序列所取得的最大值。 dp[i][j]表示取i個子序列且最后一個序列的末尾為j時取得的最大值，所以對于任意一個j只有兩種情況，單獨形成一個新序列的開頭或者加入上一個序列。
#include<stdio.h>#include<algorithm>#include<iostream>using namespace std;#define MAXN 1000000#define INF 0x7fffffffint dp[MAXN + 10];int mmax[MAXN + 10];int a[MAXN + 10];int main(){ int n, m; int i, j, mmmax; while (scanf("%d%d", &m, &n) != EOF) { for (i = 1; i <= n; i++) { scanf("%d", &a[i]); mmax[i] = 0; dp[i] = 0; } mmax[0] = dp[0] = 0; for (int i = 1; i <= m; i++){ mmmax = -INF; for (int j = i; j <= n; j++){ dp[j] = max(dp[j - 1] + a[j], mmax[j - 1] + a[j]);//a[j]包含在dp[j-1]的最后一個連續段中或單獨成段 mmax[j - 1] = mmmax;//dp轉移所用到的mmax[j-1]是上一輪得到的，所以這里每次求的是上一個的防止覆蓋 mmmax = max(mmmax, dp[j]); } } B - Ignatius and the Princess IV數列中有一個數出現的次數大于數列總數數量的一半，在編程之美中看過，sort一下之后數列正中間處的數一定是那個數。
#include<iostream>#include<string.h>#include<algorithm>#include<queue>#include<set>#include<vector>using namespace std;int n;int num[1000000];int main(){ while (~scanf("%d", &n)){ for (int i = 0; i < n; i++){ scanf("%d", &num[i]); } sort(num, num + n); printf("%d/n", num[n / 2]); } return 0;}疊箱子，疊在上面的箱子必須長和寬都比下面的小，dp狀態為以該箱子為底時可以得到的最高高度。對于箱子a和b，若a的長寬都大于b，則a.dp=max(b.dp+a.h,a.dp);
#include<iostream>#include<string.h>#include<algorithm>#include<vector>using namespace std;int n;struct p{ int x, y, h,dp;}data[100];bool cmp(p a, p b){ if (a.x == b.x){ return a.y > b.y; } return a.x > b.x;}int main(){ int a, b, c; int t = 0; while (~scanf("%d", &n),n){ t++; for (int i = 0; i < n; i++){ scanf("%d%d%d",&a,&b,&c ); if (a>b){ swap(a, b); } if (a > c){ swap(a, c); } if (b > c){ swap(b, c); } data[i * 3].x = a, data[i * 3].y = b, data[i * 3].h=data[i*3].dp= c; data[i * 3+1].x = a, data[i * 3+1].y = c, data[i * 3+1].h =data[i*3+1].dp= b; data[i * 3+2].x = b, data[i * 3+2].y = c, data[i * 3+2].h =data[i*3+2].dp= a; } int k = 3 * n; int ans = 0; sort(data, data + k,cmp); for (int i = 0; i < k; i++){ for (int j = 0; j < i; j++){ if (data[i].x < data[j].x&&data[i].y < data[j].y){ data[i].dp = max(data[i].dp, data[j].dp + data[i].h); ans = max(ans, data[i].dp); } } } printf("Case %d: maximum height = %d/n",t,ans ); } return 0;}之前寫過的了。
經典的dp題，但是得剛剛好才行，所以dp初始化為-1。
#include<iostream>#include<stdio.h>#include<string>#include<string.h>#include<algorithm>#include<vector>using namespace std;int e, f,n,total;int v[505];int need[505];int dp[10005];int main(){ int t; scanf("%d", &t); while (t--){ scanf("%d%d", &e, &f); total = f - e; scanf("%d", &n); memset(dp, 0x3f, sizeof(dp)); for (int i = 0; i < n; i++){ scanf("%d %d", &v[i], &need[i]); } dp[0] = 0; for (int i = 0; i < n; i++){ for (int j = need[i]; j <= total; j++){ dp[j] = min(dp[j], dp[j - need[i]] + v[i]); } } if (dp[total] == 0x3f3f3f3f){ printf("This is impossible./n"); } else{ printf("The minimum amount of money in the piggy-bank is %d./n", dp[total]); } } return 0;}dp[j][i]為第i秒在j位置時可以得到餡餅得最大值，dp[j][i] = max(max(dp[j - 1][i - 1], dp[j + 1][i - 1]), dp[j][i - 1])+v[j][i]；
#include<iostream>#include<string.h>#include<algorithm>#include<queue>#include<set>#include<string>#include<vector>using namespace std;const int maxt = 100005;int n,t;int v[13][maxt];int dp[13][maxt];int main(){ int a, b; while (scanf("%d", &n), n != 0){ memset(v, 0, sizeof(v)); t = 0; for (int i = 0; i < n; i++){ scanf("%d%d", &a, &b); v[a+1][b]++; t = max(t, b); } for (int i = 0; i < 13; i++){ for (int j = 0; j <= t; j++){ dp[i][j] = -10000; } } dp[6][0] = 0; for (int i = 1; i <= t; i++){ for (int j = 1; j <= 11; j++){ dp[j][i] = max(max(dp[j - 1][i - 1], dp[j + 1][i - 1]), dp[j][i - 1])+v[j][i]; } } int ans = 0; for (int i = 1; i < 12; i++){ ans = max(ans, dp[i][t]); } printf("%d/n", ans); } return 0;}賣票可以單個人單個人賣，也可以兩個一起賣，已知每個人單人所用的時間和相鄰兩個人所需的時間，求最少用時，dp[i] = min(dp[i - 1] + single[i], dp[i - 2] + doubl[i - 1]);
#include<iostream>#include<string.h>#include<algorithm>#include<stdio.h>#include<vector>#include<iomanip>using namespace std;int n, m;int single[2005];int doubl[2005];int dp[2005];int main(){ int t; scanf("%d", &t); while (t--){ scanf("%d", &m); for (int i = 1; i <= m; i++){ scanf("%d", &single[i]); } for (int i = 1; i <= m - 1; i++){ scanf("%d", &doubl[i]); } memset(dp, 0x3f, sizeof(dp)); dp[0] = 0; dp[1] = single[1]; for (int i = 2; i <= m; i++){ dp[i] = min(dp[i - 1] + single[i], dp[i - 2] + doubl[i - 1]); } int ans = dp[m]; int h = 0, min = 0, sec = 0; sec = ans % 60, ans /= 60; min = ans % 60; ans /= 60; h = (ans + 8)%24; bool mor = true; if (h > 12){ h -= 12; mor = false; } cout << setw(2) << setfill('0') << h << ':' << setw(2) << setfill('0') << min <<':' << setw(2) << setfill('0') << sec << ' ' << (mor ? "am" : "pm") << endl; } return 0;}最少不上升序列分割數等于最長上升序列的長度。（不會證= =）
#include<iostream>#include<string.h>#include<algorithm>#include<stdio.h>#include<vector>#include<iomanip>using namespace std;int n;int data[1000005];int a[1000005];int main(){ while (~scanf("%d", &n)){ if (n == 0){ printf("0/n"); continue; } for (int i = 0; i < n; i++){ scanf("%d", &data[i]); } int ans = 0; a[0] = data[0]; for (int i = 1; i < n; i++){ if (data[i]>a[ans]){ a[++ans] = data[i]; continue; } else{ for (int j = 0; j <= ans; j++){ if (data[i] <= a[j]){ a[j] = data[i]; break; } } } } printf("%d/n", ans+1); } return 0;}要保存路徑，所以用pre數組保存前一個，
#include<iostream>#include<string.h>#include<algorithm>#include<stdio.h>//adawdawdusing namespace std;int n;struct pp{ int l, r,num;}p[1005];int dp[1005];int pre[1005];bool cmp(pp a, pp b){ if (a.l == b.l){ return a.r > b.r; } else return a.l < b.l;}int main(){ n = 1; while (~scanf("%d%d",&p[n].l,&p[n].r)){ dp[n] = 1; p[n++].num = n; } sort(p+1, p + n, cmp); int maxlen = 0, maxid = 0; //dp[1] = 1; for (int i = 1; i < n; i++){ for (int j = 1; j <i; j++){ if (p[i].l > p[j].l&&p[i].r<p[j].r&&dp[j] + 1>dp[i]){ dp[i] = dp[j] + 1; pre[i] = j; } } } for (int i = 1; i < n; i++){ if (dp[i] > maxlen){ maxlen = dp[i]; maxid = i; } } for (int i = maxlen; i >= 1; i--){ dp[i] = p[maxid].num; maxid = pre[maxid]; } printf("%d/n", maxlen); for (int i = 1; i <= maxlen; i++){ printf("%d",dp[i]); if (i < maxlen){ printf("/n"); } } return 0;}難度挺大的，自己寫的一直wa。dp[a][b]為選擇a個人之后總控方分數-總辯方分數為b時控辯分和的最大值。 同時用path數組保存路徑。
經典題目了， if (a[i] == b[j]){dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1);} else{dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);}
#include<iostream>#include<string.h>#include<algorithm>#include<stdio.h>#include<string>using namespace std;string a, b;int dp[1005][1005];//dp[a][b]字符串A的前a位和B的前b位最大公共長度int main(){ while (cin >> a >> b){ int lena = a.length(); int lenb = b.length(); memset(dp, 0, sizeof(dp)); for (int i = 0; i < lena; i++){ for (int j = 0; j < lenb; j++){ if (a[i] == b[j]){ dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1); } else{ dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]); } } } printf("%d/n", dp[lena][lenb]); } return 0;}這題不大懂得用dp解，看人別人的題解用的遞歸搜索，dfs（x,y,z）為從z橋的x坐標（x,y）處下落到下一塊木板的用時。
#include<stdio.h>#include<string.h>#include<algorithm>#include<iostream>using namespace std;//dawdawdawint n, bx, by, maxd;const int inf = 10000000;int l[1005];int r[1005];struct ss{ int l, r, h;}s[1005];bool cmp(ss a, ss b){ return a.h > b.h; }int dfs(int x, int y, int cnt){//計算從當前板邊緣下落到下一塊板然后走到左右邊緣要再次下落的過程 int nid=0; for (int i = cnt + 1; i <= n; i++){ if (s[i].l <= x&&s[i].r >= x&&s[i].h < y){ if (y - s[i].h>maxd){ return inf; } else{ nid = i; break; } } } if (nid == 0){ return (y>maxd?inf:y); } if (l[nid] == -1){ l[nid] = dfs(s[nid].l, s[nid].h, nid); r[nid] = dfs(s[nid].r, s[nid].h, nid); } int time = 0; time = min(l[nid] + x - s[nid].l, r[nid] + s[nid].r - x); time += y - s[nid].h; return time;}int main(){ int t; scanf("%d", &t); while (t--){ scanf("%d%d%d%d", &n, &bx, &by, &maxd); memset(l, -1, sizeof(l)); memset(r, -1, sizeof(r)); for (int i = 1; i <= n; i++){ scanf("%d%d%d", &s[i].l, &s[i].r, &s[i].h); } sort(s + 1, s + n + 1, cmp); printf("%d/n", dfs(bx, by, 0)); } return 0;}最長上升子序列長度，用前面的導彈防御題的代碼就能ac。
每天只能賣序列頭或者尾的東西，價格為該物品的價格乘上天數。 dp[m][k]為第m天賣剩下開頭為第k個的長度位n-m的序列所能獲得的最大收入， dp[i][j] = max(dp[i - 1][j - 1] + s[j - 1] * i, dp[i - 1][j] + s[n - i + j]*i);
#include<iostream>#include<string.h>#include<algorithm>#include<stdio.h>#include<vector>#include<iomanip>using namespace std;int n;int s[2005];int dp[2005][2005];//dp[m][k]第m天剩下開頭為第k個的長度位n-mint main(){ scanf("%d", &n); for (int i = 1; i <= n; i++)scanf("%d", &s[i]); for (int i = 1; i <= n; i++){ for (int j = 1; j <= i + 1; j++){ dp[i][j] = max(dp[i - 1][j - 1] + s[j - 1] * i, dp[i - 1][j] + s[n - i + j]*i); } } int ans = 0; for (int i = 1; i <= n; i++){ ans = max(ans, dp[n][i]); } printf("%d", ans); return 0;}也是看了別人的題解，用的dfs。
求最大對稱子矩陣，dp[i][j]為以第i行j列為子矩陣的左下角，所能得到的最大對稱子矩陣的邊長，所以枚舉ij，求出其上方和右方的最大相同長度，然后與dp[i-1][j+1]比較來維護dp[i][j]
#include<iostream>#include<stdio.h>using namespace std;int n;char m[1005][1005];int dp[1005][1005];int main(){ while (~scanf("%d", &n), n){ int ans = 1; for (int i = 0; i < n; i++){ scanf("%s", m[i]); for (int j = 0; j < n; j++){ dp[i][j] = 1; } } for (int i = 1; i < n; i++){ for (int j = 0; j < n-1; j++){ int k = 1; while (j + k < n&&i - k >= 0 && m[i][j + k] == m[i - k][j]){ k++; } if (k >= dp[i - 1][j + 1] + 1)dp[i][j] = dp[i - 1][j + 1] + 1; else{ dp[i][j] = k; } ans = max(ans, dp[i][j]); } } printf("%d/n", ans); } return 0;}擠牛奶，有開始時間結束時間和效率，每次工作完還要休息。求給定時間能獲得的最大值。 按結束時間排序，然后順序維護一邊dp就行。 細節注意比較簡單。
#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;int n,m,r;struct ss{ int beg, end, val;}s[1005];int dp[1000005];bool cmp(ss a, ss b){ return a.end < b.end;}int main(){ scanf("%d%d%d", &n, &m, &r); n += r; for (int i = 0; i < m; i++){ scanf("%d%d%d", &s[i].beg, &s[i].end, &s[i].val); s[i].beg += r; s[i].end += r; } sort(s, s + m, cmp); int maxval = 0; int time = 0; for (int i = 0; i <= m; i++){ for (; time < s[i].end; time++){ dp[time] = maxval; } if (time>n)break; maxval = max(maxval, dp[s[i].beg - r] + s[i].val); } printf("%d", maxval); return 0;}看了題解的，數據較水，給定的數列，問消耗最少是其變成非嚴格單調的，代碼只得出了非嚴格遞增的最小消耗。使用了離散化，因為數據有些值過大不能開出這么大的數組，而且非嚴格單調只需要將某個數字改成相鄰數字一樣便能得到最優解。還用了二維滾動數組減少空間消耗。 dp[i][j]為前i個維護成非嚴格遞增時末尾為b[j]時消耗的最小值。
#include<stdio.h>#include<algorithm>#include<iostream>#include<cmath>using namespace std;const long long inf = 0x3f3f3f3f3f;int n;long long a[2005],b[2005];long long dp[2][2005];//二維滾動數組int main(){ while (~scanf("%d", &n)){ for (int i = 0; i < n; i++){ scanf("%d", &a[i]); b[i] = a[i]; } sort(b, b + n); //memset(dp, 0, sizeof(dp)); for (int i = 0; i < n; i++){ dp[0][i] = labs(a[0] - b[i]); } for (int i = 1; i < n; i++){ long long cnt = inf; for (int j = 0; j < n; j++){ cnt = min(cnt, dp[(i + 1) % 2][j]); dp[i % 2][j] = cnt+labs(a[i]-b[j]); } } long long ans = inf; for (int i = 0; i < n; i++){ ans = min(ans, dp[(n + 1) % 2][i]); } printf("%d/n", ans); } return 0;}新聞熱點
疑難解答
