DP综合练习

区间DP

P1775 石子合并（弱化版）

P1880 [NOI1995] 石子合并

• 环形区间DP：取模或将圆环转换成两倍线性区间

P1063 NOIP2006 提高组 能量项链

P1040 加分二叉树

矩形DP

P1387 最大正方形

• \(dp[i][j][k]\) 表示以\((i,j)\)为左上角，边长为\(k\)的正方形是否有效
• 其转移过程如图：

代码

#include<iostream>
using namespace std;
const int N = 105;

int n, m, ans;
bool f[N][N][N];

int main(){

    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> f[i][j][1];
            if(f[i][j][1]) ans = 1;
        }
    }

    for(int i = 2; i <= n; i++){
        for(int x = 1; x + i - 1 <= n; x++){
            for(int y = 1; y + i - 1 <= m; y++){
                f[x][y][i] = f[x][y][i - 1] &&
                            f[x][y + 1][i - 1] &&
                            f[x + 1][y][i - 1] &&
                            f[x + 1][y + 1][i - 1];
                if(f[x][y][i]){
                    ans = max(ans, i);
                }
            }
        }
    }

    cout << ans;

    return 0;
}

P2701巨大牛棚

代码

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1005;

int n, t, ans;
int dp[N][N];
bool tree[N][N];

int main(){

    cin >> n >> t;
    for(int i = 1; i <= t; i++){
        int x, y;
        cin >> x >> y;
        tree[x][y] = 1;
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(tree[i][j]) continue;
            dp[i][j] = min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
            ans = max(ans, dp[i][j]);
        }
    }


    cout << ans;

    return 0;
}

P1736 创意吃鱼法

代码

#include<iostream>
#include<cstring>
using namespace std;
const int N = 2510;

int n, m, ans;
int fish[N][N];
int dp[N][N], px[N][N], py[N][N];

int main(){

    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> fish[i][j];
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(fish[i][j]) continue;
            px[i][j] = px[i - 1][j] + 1;
            py[i][j] = py[i][j - 1] + 1;
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(!fish[i][j]) continue;
            dp[i][j] = min(dp[i - 1][j - 1], min(px[i - 1][j], py[i][j - 1])) + 1;
            ans = max(ans, dp[i][j]);
        }
    }

    memset(py, 0, sizeof(py));
    for(int i = 1; i <= n; i++){
        for(int j = m; j >= 1; j--){
            if(fish[i][j]) continue;
            py[i][j] = py[i][j + 1] + 1;
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = m; j >= 1; j--){
            if(!fish[i][j]) continue;
            dp[i][j] = min(dp[i - 1][j + 1], min(px[i - 1][j], py[i][j + 1])) + 1;
            ans = max(ans, dp[i][j]);
        }
    }

    cout << ans;

    return 0;
}

其他DP

P1006 传纸条

• 采用\(i+j-1\)作为dp数组的第一维，斜向考虑

代码

#include<iostream>
using namespace std;
const int N = 110;

int dx1[] = {-1, -1, 0, 0};
int dx2[] = {-1, 0, 0, -1};

int n, m;
int a[N][N], f[N][N][N];

bool in_bound(int k, int y){

    int x = k - y;
    return 1 <= x && x <= n && 1 <= y && y <= m;

}

int main(){

    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> a[i][j];
        }
    }

    f[3][1][2] = a[1][2] + a[2][1];
    for(int k = 4; k < n + m; k++){
        for(int i = 1; i < m; i++){
            if(!in_bound(k, i)) continue;
            for(int j = i + 1; j <= m; j++){
                if(!in_bound(k, j)) continue;
                for(int l = 0; l < 4; l++){
                    int ii = i + dx1[l];
                    int jj = j + dx2[l];
                    if(ii == jj) continue;
                    if(in_bound(k - 1, ii) && in_bound(k - 1, jj))
                        f[k][i][j] = max(f[k][i][j], f[k - 1][ii][jj] + a[k - i][i] + a[k - j][j]);
                }
            }
        }
    }

    cout << f[n + m - 1][m - 1][m];

    return 0;
}

错误点：

P1004 [NOIP2000 提高组] 方格取数

思路和P1006类似，用\(i+j\)做dp的第一维

代码

#include<iostream>
#include<cstring>
using namespace std;
const int N = 25;

int n;
int a[N][N];
int dp[N][N][N];

int main(){

    cin >> n;
    while(true){
        int x, y, v;
        cin >> x >> y >> v;
        if(v == 0) break;
        a[x][y] = v;
    }

    memset(dp, -0x3f, sizeof(dp));
    dp[2][1][1] = a[1][1];

    for(int i = 3; i <= 2 * n; i++){
        for(int j = 1; j <= min(i - 1, n); j++){
            for(int k = 1; k <= min(i - 1, n); k++){
                dp[i][j][k] = max(max(dp[i - 1][j][k], dp[i - 1][j - 1][k]), 
                          max(dp[i - 1][j][k - 1], dp[i - 1][j - 1][k - 1]));
                if(j == k) dp[i][j][k] += a[j][i - j];
                else dp[i][j][k] += a[j][i - j] + a[k][i - k];
            }
        }
    }

    cout << dp[2 * n][n][n] << endl;

    return 0;
}

P1541 [NOIP2010 提高组] 乌龟棋

• 观察题面容易想到用剩余四种卡牌的数量作为状态，由这四个数字就能直接计算出棋子当前的位置，不需要再把位置作为一个维度
• 仔细审题再写代码，棋子从哪个位置开始，得分的初值是多少

代码

#include<iostream>
#include<cstring>
using namespace std;
const int N = 400;
const int M = 50;

int n, m;
int w[N], cnt[5];
int dp[M][M][M][M];

int main(){

    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> w[i];
    }
    for(int i = 1; i <= m; i++){
        int tmp;
        cin >> tmp;
        cnt[tmp]++;
    }


    dp[0][0][0][0] = w[1];
    for(int c1 = 0; c1 <= cnt[1]; c1++){
        for(int c2 = 0; c2 <= cnt[2]; c2++){
            for(int c3 = 0; c3 <= cnt[3]; c3++){
                for(int c4 = 0; c4 <= cnt[4]; c4++){
                    int num = w[1 + c1 + c2 * 2 + c3 * 3 + c4 * 4];
                    if(c1 >= 1) dp[c1][c2][c3][c4] = max(dp[c1][c2][c3][c4], dp[c1-1][c2][c3][c4] + num);
                    if(c2 >= 1) dp[c1][c2][c3][c4] = max(dp[c1][c2][c3][c4], dp[c1][c2-1][c3][c4] + num);
                    if(c3 >= 1) dp[c1][c2][c3][c4] = max(dp[c1][c2][c3][c4], dp[c1][c2][c3-1][c4] + num);
                    if(c4 >= 1) dp[c1][c2][c3][c4] = max(dp[c1][c2][c3][c4], dp[c1][c2][c3][c4-1] + num);
                }
            }
        }
    }

    cout << dp[cnt[1]][cnt[2]][cnt[3]][cnt[4]] << endl;

    return 0;
}

P1508 Likecloud-吃、吃、吃

代码

#include<iostream>
using namespace std;

const int N = 205;
int a[N][N], f[N][N];

int main(){

    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> a[i][j];
        }
    }

    for(int i = 1; i <= n + 1; i++){
        for(int j = 1; j <= m; j++){
            f[i][j] = max(f[i - 1][j], max(f[i - 1][j - 1], f[i - 1][j + 1])) + a[i][j];
        }
    }
    cout << f[n + 1][(m + 1) / 2];

    return 0;
}

P1417 烹调方案

代码

#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;

const int N = 205;

struct node{

    ll a, b, c;

};

bool cmp(node i, node j){
    return j.b * i.c < i.b * j.c;
}

int main(){

    ll t, n;
    node a[N];
    cin >> t >> n;

    for(ll i = 1; i <= n; i++){
        cin >> a[i].a;
    }
    for(ll i = 1; i <= n; i++){
        cin >> a[i].b;
    }
    for(ll i = 1; i <= n; i++){
        cin >> a[i].c;
    }

    sort(a + 1, a + n + 1, cmp);

    ll f[100000] = {0}, ans = 0;
    for(ll i = 1; i <= n; i++){
        for(ll j = t; j >= a[i].c; j--){
            f[j] = max(f[j], f[j - a[i].c] + a[i].a - j * a[i].b);
            ans = max(ans, f[j]);
        }
    }

    cout << ans;

    return 0;
}

P1782 旅行商的背包

P1858 多人背包

代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 205;

int n, V, K;
int v[N], w[N];
int dp[5005][55 * 2];

bool cmp(int a, int b){
    return a > b;
}

int main(){

    cin >> K >> V >> n;
//注意要初始化
//因为背包必须装满（题目要求）
    memset(dp, -0x3f, sizeof(dp));
    dp[0][1] = 0;

    for(int i = 1; i <= n; i++){
        cin >> v[i] >> w[i];
    }

    for(int i = 1; i <= n; i++){
        for(int j = V; j >= v[i]; j--){
//压维
            for(int k = 1; k <= K; k++){
                dp[j][k + K] = dp[j - v[i]][k] + w[i];
//                dp[j][k + K] = dp[j - v[i]][k];
            }
            sort(dp[j] + 1, dp[j] + 2 * K + 1, cmp);
//            sort(dp[j],    dp[j] + 2 * K + 1, cmp);
//            sort(dp[j] + 1, dp[j] + 2 * K,    cmp);

//不压维，会MLE
/*
            if(j >= v[i]){
                int x = 1, y = 1;
                for(int k = 1; k <= K; k++){
                    if(dp[i - 1][j - v[i]][x] + w[i] > dp[i - 1][j][y]){
                        dp[i][j][k] = dp[i - 1][j - v[i]][x++] + w[i];
                    }
                    else{
                        dp[i][j][k] = dp[i - 1][j][y++];
                    }
                }
            else{
                for(int k = 1; k <= K; k++){
                    dp[i][j][k] = dp[i - 1][j][k];
                }
            }
*/
        }
    }

    int res = 0;
    for(int i = 1; i <= K; i++){
        res += dp[V][i];
    }
    cout << res;

    return 0;
}

P1158 导弹拦截

代码

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 100005;

struct node{
    int a;
    int b;
};

int n;
int x1, x2, y1, y2;
int f[N];
node d[N];

bool cmp(node a, node b){
    return a.a < b.a;
}

int main(){

    cin >> x1 >> y1 >> x2 >> y2;
    cin >> n;

    for(int i = 1; i <= n; i++){
        int x, y;
        cin >> x >> y;
        d[i].a = (x - x1) * (x - x1) + (y - y1) * (y - y1);
        d[i].b = (x - x2) * (x - x2) + (y - y2) * (y - y2);
    }

    sort(d + 1, d + n + 1, cmp);

    f[n + 1] = 0;
    f[n] = d[n].b;
    for(int i = n - 1; i >= 0; i--){
        f[i] = max(f[i + 1], d[i].b);
    }

    int ans = 2147483647;
    //r1:1~i, r2:i+1~n
    for(int i = 0; i <= n; i++){
        ans = min(ans, d[i].a + f[i + 1]);
    }

    cout << ans;

    return 0;
}

P2066 机器分配

• 资源分配类动态规划（同时题目要求输出方案）

代码

#include<iostream>
using namespace std;

int n, m;
int a[20][20];
int dp[20][20]; //将前j台机器分给前i个公司的最大盈利
int ans[20][20];

void print(int i, int j){

    if(i == 0) return;
    print(i - 1, j - ans[i][j]);
    cout << i << ' ' << ans[i][j] << endl;

}

int main(){

    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> a[i][j];
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            for(int k = 0; k <= j; k++){
                if(dp[i - 1][j - k] + a[i][k] >= dp[i][j]){
                    dp[i][j] = dp[i - 1][j - k] + a[i][k];
                    ans[i][j] = k;
                }
            }
        }
    }

    cout << dp[n][m] << endl;
    print(n, m);

    return 0;
}

P1855 榨取kkksc03

代码

#include<iostream>
using namespace std;

const int N = 105;

int n, m, t;
int cm[N], ct[N];
int f[205][205];

int main(){

    cin >> n >> m >> t;
    for(int i = 1; i <= n; i++){
        cin >> cm[i] >> ct[i];
    }

    for(int i = 1; i <= n; i++){
        for(int j = m; j >= cm[i]; j--){
            for(int k = t; k >= ct[i]; k--){
                f[j][k] = max(f[j][k], f[j - cm[i]][k - ct[i]] + 1);
            }
        }
    }

    cout << f[m][t];

    return 0;
}

P2722 USACO3.1 总分 Score Inflation

代码

#include<iostream>
using namespace std;

const int N = 1E4 + 5;

int m, n;
int v[N], t[N];
int f[N];

int main(){

    cin >> m >> n;
    for(int i = 1; i <= n; i++){
        cin >> v[i] >> t[i];
    }

    for(int i = 1; i <= n; i++){
        for(int j = t[i]; j <= m; j++){
            f[j] = max(f[j], f[j - t[i]] + v[i]);
        }
    }

    cout << f[m];
    return 0;
}

P2639 USACO09OCT Bessie's Weight Problem G

代码

#include<iostream>
using namespace std;

int h, n;
int s[505];
int f[45005];

int main(){

    cin >> h >> n;
    for(int i = 1; i <= n; i++){
        cin >> s[i];
    }

    for(int i = 1; i <= n; i++){
        for(int j = h; j >= s[i]; j--){
            f[j] = max(f[j], f[j - s[i]] + s[i]);
        }
    }

    cout << f[h];

    return 0;
}

P1802 5 倍经验日

代码

#include<iostream>
using namespace std;

const int N = 1005;

int n, x;
int l[N], w[N], u[N];
int f[N];

int main(){

    cin >> n >> x;
    for(int i = 1; i <= n; i++){
        cin >> l[i] >> w[i] >> u[i];
    }
    for(int i = 1; i <= n; i++){
        for(int j = x; j >= u[i]; j--){
            f[j] = max(f[j] + l[i], f[j - u[i]] + w[i]);
        }
        for(int j = 0; j < u[i]; j++){
            f[j] += l[i];
        }
    }

    cout << f[x] * (long long)5;

    return 0;
}

USACO中的动态规划

P1470 USACO2.3 最长前缀 Longest Prefix

代码

#include<iostream>
#include<string.h>
using namespace std;

string p[210];
string s, t;

int pl = 1, sl = 1;
bool f[int(2E5) + 10] = {1}, flag;

int main(){

    while(cin >> p[pl] && p[pl] != ".") pl++;
    pl--;
    s = ' ';
    while(cin >> t){
        s += t;
    }
    sl = s.size() - 1;

    for(int i = 1; i <= sl; i++){
        if(!f[i - 1]) continue;
        for(int j = 1; j <= pl; j++){
            flag = true;
            for(int k = 0; k < p[j].size(); k++){
                if(s[i + k] != p[j][k]){
                    flag = false;
                    break;
                }
            }
            if(flag) f[i + p[j].size() - 1] = 1;
        }
    }

    int ans = 0;
    for(int i = 0; i <= sl; i++){
        if(f[i]) ans = i;
    }
    cout << ans;

    return 0;
}

P1472 USACO2.3 奶牛家谱 Cow Pedigrees

代码

#include<iostream>
#include<cstring>
using namespace std;
const int N = 205;
const int MOD = 9901;

int n, m;
int dp[N][N];

int dfs(int u, int d){

    if(dp[u][d] != -1) return dp[u][d];
    if(u == 1 && d == 1) return dp[u][d] = 1;
    if(u == 1) return dp[u][d] = 0;

    dp[u][d] = 0;
    for(int i = 1; i <= u - 2; i++){
        int j = u - 1 - i;
        int res = 0, tmp = dfs(i, d - 1);
        for(int k = 1; k < d - 1; k++){
            res += dfs(j, k) * tmp * 2;
            res %= MOD;
        }
        dp[u][d] += res;
        dp[u][d] += dfs(j, d - 1) * tmp;
        dp[u][d] %= MOD;
    }

    return dp[u][d];

}

int main(){

    memset(dp, -1, sizeof(dp));
    cin >> n >> m;

    cout << dfs(n, m);

    return 0;
}

[P1474 USACO2.3]Money System / [USACO07OCT]Cow Cash G

P1578 奶牛浴场

思路

一个“极大”的浴场一定四条边都受到限制，不能再扩展了

代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 5E3 + 10;

struct Point{
    int x;
    int y;
};

int l, w, n, ans;
Point pt[N];

bool cmp1(Point pt1, Point pt2){
    if(pt1.x < pt2.x) return true;
    if(pt1.x == pt2.x && pt1.y < pt2.y) return true;
    return false;
}

bool cmp2(Point pt1, Point pt2){
    if(pt1.y < pt2.y) return true;
    if(pt1.y == pt2.y && pt1.x < pt2.x) return true;
    return false;
}

int x1, x2, y1, y2;
int main(){

    cin >> l >> w >> n;
    for(int i = 1; i <= n; i++){
        cin >> pt[i].x >> pt[i].y;
    }
    pt[++n] = {0, 0};
    pt[++n] = {l, 0};
    pt[++n] = {0, w};
    pt[++n] = {l, w};

    sort(pt + 1, pt + 1 + n, cmp1);

    for(int i = 1; i <= n; i++){
        x1 = pt[i].x;
        y1 = 0;
        y2 = w;
        for(int j = i + 1; j <= n; j++){
            x2 = pt[j].x;
            ans = max(ans, (y2 - y1) * (x2 - x1));
            if(pt[j].y > pt[i].y) y2 = min(y2, pt[j].y);
            else y1 = max(y1, pt[j].y);
        }
    }

    for(int i = n; i >= 1; i--){
        x2 = pt[i].x;
        y1 = 0;
        y2 = w;
        for(int j = i - 1; j >= 1; j--){
            x1 = pt[j].x;
            ans = max(ans, (y2 - y1) * (x2 - x1));
            if(pt[j].y > pt[i].y) y2 = min(y2, pt[j].y);
            else y1 = max(y1, pt[j].y);
        }
    }

    sort(pt + 1, pt + 1 + n, cmp2);

    for(int i = 1; i <= n - 1; i++){
        ans = max(ans, l * (pt[i + 1].y - pt[i].y));
    }

    cout << ans << endl;

    return 0;
}

P1879 USACO06NOV Corn Fields G

P2690 USACO04NOV Apple Catching G

P2727 USACO3.2 01串 Stringsobits

P2736USACO3.4 “破锣摇滚”乐队 Raucous Rockers

P2921 USACO08DEC Trick or Treat on the Farm G

P2925 USACO08DEC Hay For Sale S

DAG上的动态规划

T72672 矩形嵌套

代码

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int N = 1005;

int t, n;
int a[N], b[N], dp[N];
vector<int> adj[N];

bool cmp(int i, int j){
    return (a[i] < a[j] && b[i] < b[j]) || (a[i] < b[j] && b[i] < a[j]);
}

int dfs(int u){

    if(dp[u]) return dp[u];
    dp[u] = 1;
    for(auto v : adj[u]){
        dp[u] = max(dp[u], dfs(v) + 1);
    }
    return dp[u];

}

int main(){

    cin >> t;
    while(t--){
        memset(dp, 0, sizeof(dp));
        cin >> n;
        for(int i = 1; i <= n; i++){
            cin >> a[i] >> b[i];
            adj[i].clear();
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(cmp(i, j)) adj[j].push_back(i);
            }
        }
        int ans = 0;
        for(int i = 1; i <= n; i++){
            ans = max(ans, dfs(i));
        }
        cout << ans << endl;
    }

    return 0;
}

P2583 地铁间谍

代码

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1005;
//数组开小了，开255个不行

long long n, t, m1, m2, cnt = 1;
long long tm[N], train1[N][N], train2[N][N], dp[N][N];

int main(){

    while(true){
        memset(dp, 0x3f, sizeof(dp));
        memset(train1, 0, sizeof(train1));
        memset(train2, 0, sizeof(train2));
        memset(tm, 0, sizeof(tm));
        cin >> n;
        if(n == 0) break;
        cin >> t;
        for(int i = 1; i < n; i++){
            cin >> tm[i];
        }
        cin >> m1;

        for(int i = 1; i <= m1; i++){
            int d;
            cin >> d;
            for(int j = 1; j <= n; j++){
                train1[j][d] = 1;
                d += tm[j];
            }
        }
        cin >> m2;
        for(int i = 1; i <= m2; i++){
            int e;
            cin >> e;
            for(int j = n; j >= 1; j--){
                train2[j][e] = 1;
                e += tm[j - 1];
            }
        }

        dp[n][t] = 0;

        for(int j = t - 1; j >= 0; j--){
            for(int i = 1; i <= n; i++){
                if(j + 1 <= t) dp[i][j] = dp[i][j + 1] + 1;
                if(i + 1 <= n && j + tm[i] <= t     && train1[i][j]) dp[i][j] = min(dp[i][j], dp[i + 1][j + tm[i]]);
                if(i - 1 >= 1 && j + tm[i - 1] <= t && train2[i][j]) dp[i][j] = min(dp[i][j], dp[i - 1][j + tm[i - 1]]);
            }
        }
        cout << "Case Number " << cnt++ << ": ";
        if(dp[1][0] > 5E9) cout << "impossible\n";
        else cout << dp[1][0] << endl;
    }

    return 0;
}

P3408 恋爱

代码

#include<iostream>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
const ll N = 500005;

ll n, t, c;
ll a[N], b[N], dp[N];
vector<ll> adj[N];

ll dfs(ll root){

    ll cnt = 0, ans = 0;
    for(auto v : adj[root]){
        b[++cnt] = dfs(v);
    }
    if(cnt == 0){
        return dp[root] = a[root];
    }
    sort(b + 1, b + 1 + cnt);
    for(ll i = 1; i * t < a[i] * cnt; i++) ans += b[i];

    return dp[root] = ans;
}

int main(){

    cin >> n >> t >> c;
    a[0] = c;
    for(ll i = 1; i <= n; i++){
        ll b;
        cin >> b >> a[i];
        adj[b].push_back(i);
    }

    cout << dfs(0) << endl;

    for(int i = 0; i <= n; i++){
        cout << dp[i] << ' ';
    }

    return 0;
}

P1352 没有上司的舞会

代码

#include<iostream>
#include<vector>
using namespace std;
const int N = 6E3 + 10;

int n, root;
int r[N], f[N][2];
bool flag[N];
vector<int> adj[N];

void dfs(int u){

    for(auto v : adj[u]){
        dfs(v);
        f[u][0] += max(f[v][0], f[v][1]);
        f[u][1] += f[v][0];
    }
    f[u][1] += r[u];

}

int main(){

    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> r[i];
    }
    for(int i = 1; i <= n - 1; i++){
        int l, k;
        cin >> l >> k;
        flag[l] = 1;
        adj[k].push_back(l);
    }

    for(int i = 1; i <= n; i++){
        if(flag[i] == 0){
            root = i;
            break;
        }
    }

    dfs(root);

    cout << max(f[root][0], f[root][1]);

    return 0;
}

P2015 二叉苹果树

P1272 重建道路

P1273 有线电视网

代码

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int N = 3005;

struct Edge{
    int v;
    int w;
};

int n, m;
int f[N][N], c[N];
vector<Edge> adj[N];

int dfs(int u){

    if(u >= n - m + 1){
        f[u][1] = c[u];
        return 1;
    }

    int res = 0;
    for(auto e : adj[u]){
        int v = e.v;
        int w = e.w;
        int k = dfs(v);
        for(int i = res + k; i >= 0; i--){
//------------------------------------------------------------------------------------------------------------------------
            for(int j = i - k; j <= min(res, i); j++){ //这里，j的范围需要保证左右两部分的用户数量均不超过其总共的用户数量
                f[u][i] = max(f[u][i], f[u][j] + f[v][i - j] - w);
            }
        }
        res += k;
    }

    return res;
}

int main(){

    memset(f, -0x3f, sizeof(f));

    cin >> n >> m;
    for(int u = 1; u <= n - m; u++){
        f[u][0] = 0;
        int k;
        cin >> k;
        while(k--){
            int v, w;
            cin >> v >> w;
            adj[u].push_back({v, w});
        }
    }

    for(int i = n - m + 1; i <= n; i++){
        cin >> c[i];
    }

    dfs(1);

    for(int i = m; i >= 0; i--){
        if(f[1][i] >= 0){
            cout << i;
            return 0;
        }
    }

    return 0;
}

P2014 CTSC1997 选课

P2016 战略游戏