# Dynamic Programming - HDU

## HDU 2955

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45  #include #include using namespace std; const int MAX = 10240; int pValue[MAX]; double pCost[MAX], f[MAX]; int main() { int T, M, V; double P; cin >> T; for(int k = 1; k <= T; k++) { f[0] = 1; V = 0; for(int i = 1; i < MAX; i++) { f[i] = -1; } cin >> P >> M; for(int i = 1; i <= M; i++) { cin >> pValue[i] >> pCost[i]; pCost[i] = 1 - pCost[i]; V += pValue[i]; } for(int i = 1; i <= M; i++) { for(int j = V; j >= pValue[i]; j--) { if(f[j - pValue[i]] != -1) { f[j] = max(f[j - pValue[i]] * pCost[i], f[j]); } } } int ans = 0; for(int i = 0; i <= V; i++) { if(1 - f[i] <= P) { ans = i; } } cout << ans << endl; } return 0; } 

## HDU 1864

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58  #include #include #include using namespace std; const int MAX = 3840000; int pHash[32]; int f[MAX], pValue[MAX], pCost[MAX]; int main() { int N, M, V, nCnt; string strTmp; double Q; while(cin >> Q >> N && N) { V = Q * 100; nCnt = 0; memset(f, 0, sizeof(f)); for(int i = 1; i <= N; i++) { int nSum = 0; bool bFlag = true; cin >> M; memset(pHash, 0, sizeof(pHash)); for(int j = 1; j <= M; j++) { cin >> strTmp; pHash[strTmp[0] - 'A'] += atof(strTmp.substr(2, strTmp.length() - 2).c_str()) * 100; } for(int j = 0; j < 32; j++) { if(j >= 3 && pHash[j]) { bFlag = false; } nSum += pHash[j]; if(pHash[j] > 60000) { bFlag = false;} } if(nSum > 100000) { bFlag = false; } if(bFlag) { nCnt++; pValue[nCnt] = pCost[nCnt] = nSum; } } for(int i = 1; i <= nCnt; i++) { for(int j = V; j >= pCost[i]; j--) { f[j] = max(f[j - pCost[i]] + pValue[i], f[j]); } } int ans = 0; for(int i = 0; i <= V; i++) { ans = max(ans, f[i]); } cout << ans / 100 << "."; if(ans % 100 < 10 ) { cout << "0"; } cout << ans % 100 << endl; } return 0; } 

## HDU 1231

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35  #include #include using namespace std; const int MAX = 10240; int l, r, ans, al, ar; int pData[MAX], f[MAX]; int main() { ios::sync_with_stdio(false); int K; while(cin >> K) { if(K == 0) { break; } for(int i = 1; i <= K; i++) { cin >> pData[i]; } l = r = al = ar = 1; ans = pData[1]; memset(f, 0, sizeof(f)); for(int i = 1; i <= K; i++) { if(f[i - 1] + pData[i] > pData[i]) { f[i] = f[i - 1] + pData[i]; r = i; } else { f[i] = pData[i]; l = r = i; } if(f[i] > ans) { ans = f[i]; al = l; ar = r; } } if(ans >= 0) { cout << ans << " " << pData[al] << " " << pData[ar] << endl; } else { cout << 0 << " " << pData[1] << " " << pData[K] << endl; } } return 0; } 

## HDU 1003

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38  #include #include using namespace std; const int MAX = 102400; int l, r, ans, al, ar; int pData[MAX], f[MAX]; int main() { ios::sync_with_stdio(false); int K, N; while(cin >> K) { for(int i = 1; i <= K; i++) { cin >> N; for(int j = 1; j <= N; j++) { cin >> pData[j]; } l = r = al = ar = 1; ans = pData[1]; memset(f, 0, sizeof(f)); for(int j = 1; j <= N; j++) { if(f[j - 1] + pData[j] >= pData[j]) // 此处为非严格大于 { f[j] = f[j - 1] + pData[j]; r = j; } else { f[j] = pData[j]; l = r = j; } if(f[j] > ans) { ans = f[j]; al = l; ar = r; } } cout << "Case " << i << ":" << endl; cout << ans << " " << al << " " << ar << endl; if(i != K) { cout << endl; } } } return 0; } 

## HDU 1506

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47  #include const int MAX = 102400; long long pData[MAX], pLeft[MAX], pRight[MAX]; long long max(long long x, long long y); int main() { int N; long long ans; while(scanf("%I64d", &N) != EOF && N) { ans = 0; for(int i = 1; i <= N; i++) { scanf("%I64d", &pData[i]); pLeft[i] = pRight[i] = i; } for(int i = 1; i <= N; i++) { int nCur = i - 1; while(nCur >= 1 && pData[i] <= pData[nCur]) { pLeft[i] = pLeft[nCur]; nCur = pLeft[nCur] - 1; } } for(int i = N; i >= 1; i--) { int nCur = i + 1; while(nCur <= N && pData[i] <= pData[nCur]) { pRight[i] = pRight[nCur]; nCur = pRight[nCur] + 1; } } for(int i = 1; i <= N; i++) { ans = max(ans, pData[i] * (pRight[i] - pLeft[i] + 1)); } printf("%I64d\n", ans); } return 0; } long long max(long long x, long long y) { return x > y ? x : y; } 

## HDU 1505

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64  #include #include using namespace std; const int MAX = 1024; int pLeft[MAX], pRight[MAX]; int pMap[MAX][MAX], pData[MAX][MAX]; int main() { char dwTmp; int T, M, N; cin >> T; while(T) { T--; int ans = 0; memset(pData, 0, sizeof(pData)); cin >> M >> N; for(int i = 1; i <= M; i++) { for(int j = 1; j <= N; j++) { cin >> dwTmp; pMap[i][j] = (dwTmp == 'R' ? 1 : 0); if(!pMap[i][j]) { pData[i][j] = pData[i - 1][j] + 1; } else { pData[i][j] = 0; } } } for(int i = 1; i <= M; i++) { memset(pLeft, 0, sizeof(pLeft)); memset(pRight, 0, sizeof(pRight)); for(int j = 1; j <= N; j++) { pLeft[j] = pRight[j] = j; } for(int j = 1; j <= N; j++) { int nCur = j - 1; while(nCur >= 1 && pData[i][j] <= pData[i][nCur]) { pLeft[j] = pLeft[nCur]; nCur = pLeft[nCur] - 1; } } for(int j = N; j >= 1; j--) { int nCur = j + 1; while(nCur <= N && pData[i][j] <= pData[i][nCur]) { pRight[j] = pRight[nCur]; nCur = pRight[nCur] + 1; } } int nTmp = 0; for(int j = 1; j <= N; j++) { nTmp = max(nTmp, pData[i][j] * (pRight[j] - pLeft[j] + 1)); } ans = max(ans, nTmp); } cout << ans * 3 << endl; } return 0; } 

## HDU 2602

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34  #include #include using namespace std; const int MAX = 1024; int pCost[MAX], pValue[MAX], f[MAX]; int main() { int T, N, V; cin >> T; while(T) { T--; memset(f, 0, sizeof(f)); cin >> N >> V; for(int i = 1; i <= N; i++) { cin >> pValue[i]; } for(int i = 1; i <= N; i++) { cin >> pCost[i]; } for(int i = 1; i <= N; i++) { for(int j = V; j >= pCost[i]; j--) { f[j] = max(f[j - pCost[i]] + pValue[i], f[j]); } } int ans = 0; for(int i = 1; i <= V; i++) { ans = max(ans, f[i]); } cout << ans << endl; } return 0; } 

## HDU 1087

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35  #include #include using namespace std; const int MAX = 1024; int pData[MAX], f[MAX], pSum[MAX]; int main() { int N; while(cin >> N && N) { for(int i = 1; i <= N; i++) { cin >> pData[i]; } memset(f, 0, sizeof(f)); f[1] = pData[1]; for(int i = 2; i <= N; i++) { int nTmp = 0; for(int j = 1; j < i; j++) { if(pData[j] < pData[i]) { nTmp = max(nTmp, f[j]); } } f[i] = nTmp + pData[i]; } int ans = 0; for(int i = 1; i <= N; i++) { ans = max(ans, f[i]); } cout << ans << endl; } return 0; } 

## HDU 2571

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41  #include #include using namespace std; const int MAX = 1024; int pMap[MAX][MAX], f[MAX][MAX]; int main() { int C, N, M; cin >> C; while(C) { C--; memset(f, 0, sizeof(f)); cin >> N >> M; for(int i = 1; i <= N; i++) { for(int j = 1; j <= M; j++) { cin >> pMap[i][j]; } } for(int i = 1; i <= N; i++) { for(int j = 1; j <= M; j++) { int nTmp = -2147483647; if(i != 1) { nTmp = max(nTmp, f[i - 1][j]); } if(j != 1) { nTmp = max(nTmp, f[i][j - 1]); } for(int k = 2; k <= j; k++) { if(j % k == 0) { nTmp = max(nTmp, f[i][j / k]); } } f[i][j] = (nTmp == -2147483647 ? 0 : nTmp) + pMap[i][j]; } } cout << f[N][M] << endl; } return 0; } 

## HDU 1069

• 按照 $x$ 递增，然后按照 $y$ 递增，最后按照 $z$ 递增；
• 按照 $xy$ 递增。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69  #include #include #include #include using namespace std; const int MAX = 512; struct Block { Block(int _x = 0, int _y = 0, int _z = 0) { x = _x; y = _y; z = _z; } int x, y, z; }; int cmp(Block a, Block b) { if(a.x != b.x) { return a.x < b.x; } else if(a.y != b.y) { return a.y < b.y; } else { return a.z < b.z; } } bool operator < (Block a, Block b) { return a.x < b.x && a.y < b.y; } bool operator > (Block a, Block b) { return a.x > b.x && a.y > b.y; } int f[MAX], ans; vector pVec; int main() { int N, nCase = 0, x, y, z; while(cin >> N && N) { cout << "Case " << ++nCase << ": maximum height = "; ans = 0; pVec.clear(); memset(f, 0, sizeof(f)); for(int i = 1; i <= N; i++) { cin >> x >> y >> z; pVec.push_back(Block(x, y, z)); pVec.push_back(Block(x, z, y)); pVec.push_back(Block(y, x, z)); pVec.push_back(Block(y, z, x)); pVec.push_back(Block(z, x, y)); pVec.push_back(Block(z, y, x)); } sort(pVec.begin(), pVec.end(), cmp); for(int i = 0; i < pVec.size(); i++) { int nTmp = 0; for(int j = 0; j < i; j++) { if(pVec[i] < pVec[j] || pVec[i] > pVec[j]) { nTmp = max(nTmp, pVec[j].z); } } pVec[i].z += nTmp; } for(int i = 0; i < pVec.size(); i++) { ans = max(ans, pVec[i].z); } cout << ans << endl; } return 0; } 

## HDU 1171

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40  #include #include using namespace std; const int MAX = 1024000; int V, C; int pCost[MAX], f[MAX]; int main() { int N, x, y; while(cin >> N) { if(N < 0) { break; } V = 0; C = 0; memset(f, 0, sizeof(f)); for(int i = 1; i <= N; i++) { cin >> x >> y; for(int j = 1; j <= y; j++) { pCost[++C] = x; V += x; f[x] = 1; } } for(int i = 1; i <= C; i++) { for(int j = V; j >= pCost[i]; j--) { if(f[j - pCost[i]] == 1) { f[j] = 1; } } } int ans = 0; for(int i = 1; i <= V / 2; i++) { if(f[i]) { ans = i; } } cout << V - ans << " " << ans << endl; } return 0; } 

## HDU 2084

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40  #include #include using namespace std; const int MAX = 1024000; int V, C; int pCost[MAX], f[MAX]; int main() { int N, x, y; while(cin >> N) { if(N < 0) { break; } V = 0; C = 0; memset(f, 0, sizeof(f)); for(int i = 1; i <= N; i++) { cin >> x >> y; for(int j = 1; j <= y; j++) { pCost[++C] = x; V += x; f[x] = 1; } } for(int i = 1; i <= C; i++) { for(int j = V; j >= pCost[i]; j--) { if(f[j - pCost[i]] == 1) { f[j] = 1; } } } int ans = 0; for(int i = 1; i <= V / 2; i++) { if(f[i]) { ans = i; } } cout << V - ans << " " << ans << endl; } return 0; } 

## HDU 1176

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42  #include #include using namespace std; const int MAX = 102400; int f[MAX][16]; int max(int x, int y); int max(int x, int y, int z); int main() { ios::sync_with_stdio(false); int N, X, T, nCnt = 0; while(cin >> N && N) { memset(f, 0, sizeof(f)); for(int i = 1; i <= N; i++) { cin >> X >> T; f[T][X]++; nCnt = max(nCnt, T); } for(int i = nCnt - 1; i >= 0; i--) { f[i][0] += max(f[i + 1][0], f[i + 1][1]); for(int j = 1; j < 10; j++) { f[i][j] += max(f[i + 1][j - 1], f[i + 1][j], f[i + 1][j + 1]); } f[i][10] += max(f[i + 1][9], f[i + 1][10]); } cout << f[0][5] << endl; } return 0; } int max(int x, int y) { return x > y ? x : y; } int max(int x, int y, int z) { return max(x, max(y, z)); } 

## HDU 1203

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34  #include #include using namespace std; const int MAX = 10240; int pCost[MAX]; double pValue[MAX], f[MAX]; int main() { int N, M; while(cin >> N >> M) { if(N == 0 && M == 0) { break; } for(int i = 1; i <= M; i++) { cin >> pCost[i] >> pValue[i]; pValue[i] = 1 - pValue[i]; } for(int i = 0; i <= N; i++) { f[i] = 1; } for(int i = 1; i <= M; i++) { for(int j = N; j >= pCost[i]; j--) { f[j] = min(f[j - pCost[i]] * pValue[i], f[j]); } } cout << fixed << setprecision(1) << (1 - f[N]) * 100 << "%" << endl; } return 0; } 

## HDU 2159

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42  #include #include using namespace std; const int MAX = 128; int pExp[MAX], pBare[MAX]; int f[MAX][MAX]; int main() { int N, M, K, S; while(cin >> N >> M >> K >> S) { memset(f, 0, sizeof(f)); for(int i = 1; i <= K; i++) { cin >> pExp[i] >> pBare[i]; } for(int i = 1; i <= K; i++) { for(int j = 1; j <= S; j++) { for(int k = pBare[i]; k <= M; k++) { f[j][k] = max(f[j - 1][k - pBare[i]] + pExp[i], f[j][k]); } } } if(f[S][M] < N) { cout << -1 << endl; } else { int nTmp = M; for(int i = 0; i <= S; i++) { for(int j = M; j >= 0; j--) { if(f[i][j] >= N) { nTmp = min(nTmp, j); } } } cout << M - nTmp << endl; } } return 0; } 

## HDU 2577

• 第 $i$ 个字母小写：$$f[i] = \min{\left\{f[i - 1] + 1, g[i - 1] + 2\right\}},\quad g[i] = \min{\left\{f[i - 1] + 2, g[i - 1] + 2\right\}}$$
• 第 $i$ 个字母大写：$$f[i] = \min{\left\{f[i - 1] + 2, g[i - 1] + 2\right\}},\quad g[i] = \min{\left\{f[i - 1] + 2, g[i - 1] + 2\right\}}$$

• 第 1 个字母小写：$f[0] = 1,\quad g[0] = 2$
• 第 1 个字母大写：$f[0] = 2,\quad g[0] = 2$

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50  #include #include #include using namespace std; const int MAX = 128; int f[MAX], g[MAX]; bool IsUpper(char x); bool IsLower(char x); int main() { int N; string x; while(cin >> N) { for(int i = 1; i <= N; i++) { cin >> x; memset(f, 0, sizeof(f)); memset(g, 0, sizeof(g)); if(IsLower(x[0])) { f[0] = 1; g[0] = 2; } else { f[0] = 2; g[0] = 2; } for(int j = 1; j < x.length(); j++) { if(IsLower(x[j])) { f[j] = min(f[j - 1] + 1, g[j - 1] + 2); g[j] = min(f[j - 1] + 2, g[j - 1] + 2); } else { f[j] = min(f[j - 1] + 2, g[j - 1] + 2); g[j] = min(f[j - 1] + 2, g[j - 1] + 1); } } cout << min(f[x.length() - 1], g[x.length() - 1] + 1) << endl; } } return 0; } bool IsUpper(char x) { return x >= 'A' && x <= 'Z'; } bool IsLower(char x) { return x >= 'a' && x <= 'z'; } 

## HDU 2844

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45  #include #include using namespace std; const int MAX = 102400; int f[MAX]; int pValue[MAX], pData[MAX]; int main() { int N, M, nTmp; ios::sync_with_stdio(false); while(cin >> N >> M) { int nCnt = 0; if(N == 0 && M == 0) { break; } memset(f, 0, sizeof(f)); f[0] = 1; for(int i = 1; i <= N; i++) { cin >> pValue[i]; } for(int i = 1; i <= N; i++) { cin >> nTmp; for(int j = 1; j <= nTmp; j <<= 1) { pData[++nCnt] = pValue[i] * j; nTmp -= j; } if(nTmp) { pData[++nCnt] = pValue[i] * nTmp; } } for(int i = 1; i <= nCnt; i++) { for(int v = M; v >= pData[i]; v--) { if(f[v - pData[i]]) { f[v] = 1; } } } int ans = 0; for(int i = 1; i <= M; i++) { ans += f[i]; } cout << ans << endl; } return 0; }