高级动态规划：区间、树形

区间 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) {
        //printf("%d ", dp[i][i+n-1]);
        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];// 0/1
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;
}