# 区间 DP
# P1880 [NOI1995] 石子合并
| #include <stdio.h> |
| #include <string.h> |
| #include <iostream> |
| using namespace std; |
| |
| const int N = 220; |
| |
| int ans, dp[N][N], n, a[N], s[N]; |
| |
| int main() { |
| |
| scanf("%d", &n); |
| for(int i=1; i<=n; ++i) { |
| scanf("%d", a+i); |
| s[i] = s[i-1] + a[i]; |
| } |
| for(int i=1; i<=n; ++i) { |
| s[i+n] = s[i+n-1] + a[i]; |
| } |
| memset(dp, 0x3f, sizeof dp); |
| for(int i=1; i<=2*n; ++i) dp[i][i] = 0; |
| for(int l=2; l<=n; ++l) { |
| for(int i=1, j=l; j<=2*n; ++i, ++j) { |
| for(int k=i; k<j; ++k) { |
| dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + s[j] - s[i-1]); |
| } |
| } |
| } |
| ans = 0x3f3f3f3f; |
| for(int i=1; i<=n; ++i) { |
| |
| ans = min(ans, dp[i][i+n-1]); |
| } |
| printf("%d\n", ans); |
| |
| memset(dp, 0, sizeof dp); |
| for(int i=1; i<=2*n; ++i) dp[i][i] = 0; |
| for(int l=2; l<=n; ++l) { |
| for(int i=1, j=l; j<=2*n; ++i, ++j) { |
| for(int k=i; k<j; ++k) { |
| dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j] + s[j] - s[i-1]); |
| } |
| } |
| } |
| ans = 0; |
| for(int i=1; i<=n; ++i) { |
| ans = max(ans, dp[i][i+n-1]); |
| } |
| printf("%d\n", ans); |
| return 0; |
| } |
# P1063 能量项链
| #include <stdio.h> |
| #include <string.h> |
| #include <iostream> |
| using namespace std; |
| const int N = 220; |
| |
| int n, h[N], t[N], dp[N][N]; |
| int main() { |
| |
| scanf("%d", &n); |
| for(int i=1; i<=n; ++i) { |
| scanf("%d", &h[i]); |
| h[i+n] = h[i]; |
| } |
| for(int i=1; i<2*n; ++i) t[i] = h[i+1]; |
| |
| for(int l=2; l<=n; ++l) { |
| for(int i=1, j=l; j<=2*n; ++i, ++j) { |
| for(int k=i; k<j; ++k) { |
| dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j] + h[i] * t[k] * t[j]); |
| } |
| } |
| } |
| int ans = 0; |
| for(int i=1; i<=n; ++i) { |
| ans = max(ans, dp[i][i+n-1]); |
| } |
| printf("%d\n", ans); |
| return 0; |
| } |
# P3146 [USACO16OPEN]248 G
| #include <stdio.h> |
| #include <string.h> |
| #include <iostream> |
| using namespace std; |
| |
| int n, dp[300][300], ans = 0; |
| int main() { |
| |
| scanf("%d", &n); |
| for(int i=1; i<=n; ++i) { |
| scanf("%d", &dp[i][i]); |
| } |
| |
| for(int l=2; l<=n; ++l) { |
| for(int i=1, j=l; j<=n; ++i, ++j){ |
| for(int k=i; k<j; ++k) { |
| if(dp[i][k] == dp[k+1][j]) |
| dp[i][j] = max(dp[i][j], dp[i][k]+1); |
| } |
| ans = max(ans, dp[i][j]); |
| } |
| } printf("%d\n", ans); |
| return 0; |
| } |
# 树形 DP
树形 DP 三大问题：树的最大独立集 树的重心 树的最长路径
# P1352 没有上司的舞会
| #include <stdio.h> |
| #include <string.h> |
| #include <iostream> |
| #include <vector> |
| using namespace std; |
| |
| typedef vector<int>::iterator IT; |
| const int N = 6e3 + 10; |
| |
| int fa[N]; vector<int> g[N]; |
| int n, r[N]; |
| inline int fin() { |
| for(int i=1; i<=n; ++i) if(!fa[i]) return i; |
| } |
| |
| int f[N][2]; |
| void dfs(int u) { |
| f[u][0] = 0; |
| f[u][1] = r[u]; |
| for(IT it = g[u].begin(); it != g[u].end(); ++it) { |
| dfs(*it); |
| f[u][0] += max(f[*it][0], f[*it][1]); |
| f[u][1] += f[*it][0]; |
| } |
| } |
| int main() { |
| |
| scanf("%d", &n); |
| for(int i=1; i<=n; ++i) scanf("%d", r+i); |
| for(int i=1; i<n; ++i) { int l, k; |
| scanf("%d%d", &l, &k); fa[l] = k; |
| g[k].push_back(l); |
| } |
| int rt = fin(); |
| dfs(rt); |
| printf("%d", max(f[rt][0], f[rt][1])); |
| return 0; |
| } |
# P2014 [CTSC1997] 选课
| #include <stdio.h> |
| #include <string.h> |
| #include <iostream> |
| #include <vector> |
| using namespace std; |
| |
| const int N = 330; |
| vector<int> g[N]; |
| int n, m; int dp[N][N]; |
| void dfs(int u) { |
| for(vector<int>::iterator it = g[u].begin(); it != g[u].end(); it++) { |
| dfs(*it); |
| for(int j=m+1; j>1; --j) { |
| for(int k=0; k<j; ++k) |
| dp[u][j] = max(dp[u][j], dp[*it][k] + dp[u][j-k]); |
| } |
| } |
| } |
| int main() { |
| |
| scanf("%d%d", &n, &m); |
| for(int i=1; i<=n; ++i) { int k; |
| scanf("%d%d", &k, &dp[i][1]); |
| g[k].push_back(i); |
| } |
| dfs(0); |
| printf("%d\n", dp[0][m+1]); |
| return 0; |
| } |
