石子合并，入门区间dp
1 #include <cstdio> 2 #include <cstring> 3 #define maxn 305 4 #define min(a, b) a < b ? a : b 5 6 int n; 7 int sum[maxn]; 8 int f[maxn][maxn]; 9 10 int main() { 11 memset(f, 0x3f, sizeof(f)); 12 scanf("%d", &n); 13 for (int i = 1; i <= n; i++) { 14 scanf("%d", &sum[i]); 15 sum[i] += sum[i-1]; 16 f[i][i] = 0; 17 } 18 for (int len = 2; len <= n; len++) 19 for (int l = 1; l <= n-len+1; l++) { 20 int r = l + len - 1; 21 for (int k = l; k < r; k++) 22 f[l][r] = min(f[l][r], f[l][k] + f[k+1][r]); 23 f[l][r] += sum[r] - sum[l-1]; 24 } 25 printf("%d ", f[1][n]); 26 return 0; 27 }
BZOJ3229，还是石子合并，但是数据量大，换算法了。100ms以内的那个实现真是厉害！我这个是朴素的……
1 #include <cstdio> 2 #define maxn 40005 3 #define INF 0x7fffffff 4 #define R(a) scanf("%d", &a) 5 #define swap(a, b) a^=b^=a^=b 6 #define max(a, b) a > b ? a : b 7 8 int n, a[maxn], ans, k, st = 1; 9 10 int main() { 11 R(n); 12 for (int i = 1; i <= n; i++) 13 R(a[i]); 14 a[0] = a[n+1] = INF; 15 16 for (int m = n, i = 1; i < n; i++, m--) { 17 for (int j = st; j <= m; j++) 18 if (a[j-1] <= a[j+1]) { 19 k = j; 20 break; 21 } 22 23 a[k-1] += a[k]; 24 ans += a[k-1]; 25 26 for (int j = k; j <= m; j++) 27 a[j] = a[j+1]; 28 29 st = k; 30 for(k--; a[k-1] <= a[k]; swap(a[k-1], a[k]), k--); 31 32 if (k > 2 && a[k-2] <= a[k]) st = k-1; 33 else st = max(st-2, 1); 34 } 35 36 printf("%d ", ans); 37 return 0; 38 }
POJ1179，环形拆链，乘法有负数没法直接dp，石子合并的基础上再维护一个最小值即可。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 7 int n, ans = 0xcfcfcfcf; 8 int Digit[105]; 9 bool signal[105]; 10 int f[105][105], g[105][105]; 11 int record[55], t; 12 13 inline int cal(int a, int b, int k) { 14 return signal[k] ? a+b : a*b; 15 } 16 17 int main() { 18 memset(f, 0xcf, sizeof(f)); 19 memset(g, 0x3f, sizeof(g)); 20 cin >> n; 21 for (int i = 1; i <= n; i++) { 22 char ch[3]; 23 scanf("%s%d", ch, &Digit[i]); 24 signal[i-1] = signal[i-1+n] = ch[0] == 't' ? true : false; 25 f[i][i] = f[i+n][i+n] = g[i][i] = g[i+n][i+n] = Digit[i+n] = Digit[i]; 26 } 27 28 for (int len = 2; len <= n; len++) 29 for (int l = 1; l <= 2*n - len + 1; l++) { 30 int r = l + len - 1; 31 for (int k = l; k < r; k++) { 32 f[l][r] = max(f[l][r], cal(f[l][k], f[k+1][r], k)); 33 g[l][r] = min(g[l][r], cal(g[l][k], g[k+1][r], k)); 34 if (!signal[k]) { 35 f[l][r] = max(f[l][r], cal(g[l][k], g[k+1][r], k)); 36 g[l][r] = min(g[l][r], min(cal(f[l][k], g[k+1][r], k), cal(g[l][k], f[k+1][r], k))); 37 } 38 } 39 } 40 41 for (int i = 1; i <= n; i++) 42 if (ans <= f[i][i+n-1]) { 43 if (ans < f[i][i+n-1]) t = 0; 44 ans = f[i][i+n-1]; 45 record[++t] = i; 46 } 47 48 cout << ans << endl; 49 for (int i = 1; i <= t; i++) 50 printf("%d%c", record[i], " "[i==t]); 51 52 return 0; 53 }
CH金字塔，将dfs序和区间联系起来。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 #define ll long long 6 #define maxn 305 7 #define mod 1000000000 8 using namespace std; 9 10 char S[maxn]; 11 ll f[maxn][maxn]; 12 13 int solve(int l, int r) { 14 if (~f[l][r]) return f[l][r]; 15 if (l == r) return f[l][r] = 1; 16 if (S[l-1] != S[r-1]) return f[l][r] = 0; 17 18 f[l][r] = 0; 19 for (int k = l+1; k < r; k++) 20 f[l][r] = (f[l][r] + (ll)solve(l+1, k) * solve(k+1, r)) % mod; 21 return f[l][r]; 22 } 23 24 int main() { 25 cin >> S; 26 memset(f, -1, sizeof(f)); 27 printf("%d ", solve(1, strlen(S))); 28 return 0; 29 }
Joyoi没有上司的舞会，入门树形dp。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 #include <vector> 6 #define maxn 6005 7 #define pb push_back 8 using namespace std; 9 10 int n, H[maxn], f[maxn]; 11 int m[maxn][2]; 12 vector<int> v[maxn]; 13 14 int dp(int cur,int select) { 15 if (m[cur][select] != 0xcfcfcfcf) return m[cur][select]; 16 17 if (select) { 18 m[cur][select] = H[cur]; 19 for (auto i : v[cur]) 20 m[cur][select] += dp(i, 0); 21 } else { 22 m[cur][select] = 0; 23 for (auto i : v[cur]) 24 m[cur][select] += max(dp(i, 0), dp(i, 1)); 25 } 26 27 return m[cur][select]; 28 } 29 30 int main() { 31 cin >> n; 32 for (int i = 1; i <= n; i++) 33 cin >> H[i]; 34 35 int so, fa; 36 while (cin >> so >> fa && so) { 37 f[so] = fa; 38 v[fa].pb(so); 39 } 40 for (fa = 1; f[fa]; fa = f[fa]); 41 42 memset(m, 0xcf, sizeof(m)); 43 printf("%d ", max(dp(fa, 1), dp(fa, 0))); 44 return 0; 45 }
Joyoi选课，树上分组背包，果然j从0~t也是对的，没太懂书上非要倒序的意思qwq
1 #include <bits/stdc++.h> 2 #define maxn 305 3 #define pb push_back 4 using namespace std; 5 6 int n, m, score[maxn]; 7 int f[maxn][maxn]; 8 std::vector<int> v[maxn]; 9 10 int dp(int cur) { 11 f[cur][0] = 0; 12 for (auto i : v[cur]) { 13 dp(i); 14 for (int t = m; ~t; t--) 15 for (int j = 0; j <= t; j++) 16 f[cur][t] = max(f[cur][t], f[cur][t-j] + f[i][j]); 17 } 18 if (cur) 19 for (int t = m; t; t--) 20 f[cur][t] = f[cur][t-1] + score[cur]; 21 } 22 23 int main() { 24 cin >> n >> m; 25 for (int i = 1; i <= n; i++) { 26 int a; 27 cin >> a >> score[i]; 28 v[a].pb(i); 29 } 30 memset(f, 0xcf, sizeof(f)); 31 dp(0); 32 printf("%d ", f[0][m]); 33 return 0; 34 }