简单DP

HDU 5074 Hatsune Miku

Posted on

老实说有点崩溃,一场训练赛,3道dp都没出,两道还是全世界都A了
毫无疑问,又落后一截……
实在不明白他们的dp为什么这么6……

题意:
给你一个序列 a_1 a_2 a_3 a_4 …… a_n
要你求相邻两个元素在矩阵中的数值和。
矩阵已给定,但是如果序列元素为负数,则可以为任意元素。

思路:
渐渐觉得dp就是暴力……
四种情况

ary[i-1] < 0 && ary[i] < 0dp[i][j] = max(dp[i][j], dp[i - 1][k] + mat[k][j])
ary[i-1] < 0 && ary[i] > 0dp[i][ary[i]] = max(dp[i][ary[i]], dp[i - 1][j] + mat[j][ary[i]])
ary[i-1] > 0 && ary[i] < 0dp[i][j] = max(dp[i][j], dp[i - 1][ary[i - 1]] + mat[ary[i - 1]][j])
ary[i-1] > 0 && ary[i] > 0dp[i][ary[i]] = dp[i - 1][ary[i - 1]] + mat[ary[i - 1]][ary[i]]

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <queue>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
const int maxn = 110;

int mat[maxn][maxn], dp[maxn][maxn];
int ary[maxn];

int main()
{
    int T, n, m;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        range(i, 1, m) range(j, 1, m) scanf("%d", &mat[i][j]);
        range(i, 1, n) scanf("%d", ary + i);
        fill(dp, 0);
        range(i, 2, n)
        {
            if (ary[i - 1] < 0)
                if (ary[i] < 0)
                    range(j, 1, m) range(k, 1, m) dp[i][j] = max(dp[i][j], dp[i - 1][k] + mat[k][j]);
                else
                    range(j, 1, m) dp[i][ary[i]] = max(dp[i][ary[i]], dp[i - 1][j] + mat[j][ary[i]]);
            else if (ary[i] < 0)
                range(j, 1, m) dp[i][j] = max(dp[i][j], dp[i - 1][ary[i - 1]] + mat[ary[i - 1]][j]);
            else
                dp[i][ary[i]] = dp[i - 1][ary[i - 1]] + mat[ary[i - 1]][ary[i]];
        }
        int ans = 0;
        range(i, 1, m) ans = max(ans, dp[n][i]);
        printf("%d\n", ans);
    }
    return 0;
}
简单DP

POJ 1692 Crossed Matchings

Posted on

坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑!!!!!!!!!

套着二分图外套的DP题!!!!
连续栽在这个类型的题上两次!!!!!!!!

一次是上次选拔赛的时候,那时候有两道题,一道是很明显的二分图,另一道稍微隐蔽一点,但是全都栽了,我以为,建了图我就是赢家,特么的根本建不出来!!!

上次就像写一篇来阐述一下某些二分图匹配的DP解法,无奈太懒了,结果今天就又栽在这里了……

题意:
给你一张二分图,要求点权相同的点才能相互匹配,而且每个匹配有且必须要有一个权值不同的匹配与其交叉,问最大匹配数量。

思路:
很容易想去匈牙利了有木有!!!但事实却是,dp求解。 思路如下:
假设我们要考虑的状态是第一行n位置,第二行m位置,且已知之前的所有最佳状态。考虑把,n,m交叉的匹配加入到匹配集合中。那么 如果两点的权值相同则不符合要求,否则,分别向前查找各自的匹配,再与这个状态之前的状态转移即可。

如果你还不懂,那你看一遍代码肯定能懂。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
const int inf = 0x3f3f3f3f;

const int maxn = 110;

int a[maxn], b[maxn];
int dp[maxn][maxn];

int main()
{
    int n, m, T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        range(i, 1, n) scanf("%d", a + i);
        range(i, 1, m) scanf("%d", b + i);
        fill(dp, 0);
        range(i, 2, n) range(j, 2, m)
        {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            if (a[i] != b[j]) {
                int k1 = i - 1, k2 = j - 1;
                while (k1 && a[k1] != b[j])
                    k1--;
                while (k2 && a[i] != b[k2])
                    k2--;
                if (k1 && k2)
                    dp[i][j] = max(dp[i][j], dp[k1 - 1][k2 - 1] + 2);
            }
        }
        printf("%d\n", dp[n][m]);
    }
    return 0;
}
简单DP

SHU 418 A序列

Posted on

菜笔只会 O( n ^ 2 ) 的 LIS 的求法,现在补上……其实也非常好理解

这道题我记得很久很久之前就做过原题了,只要求两遍 LIS 即可,但是本来今天就OJ就很卡,好不容易交了两发,本以为两发都 WA 了 ,结果一发 waiting ,一发RE……

这里补上代码以备模板之需

题意:
找出左边递增右边递减,长度相同的子序列。

思路:
两遍LIS,同位置求最小。

#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define ll long long
#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(num, ary) memset((ary), (num), sizeof((ary)))

const int maxn = 5e+5;
int ary[maxn], st[maxn];
int dl[maxn], dr[maxn];

int main()
{
    int n;
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; i < n; i++)
            scanf("%d", ary + i);
        memset(st, 0, sizeof st);
        st[1] = ary[0], dl[0] = dr[n - 1] = 1;
        int len = 1, pos;
        for (int i = 0; i < n; i++) {
            pos = lower_bound(st, st + len, ary[i]) - st;
            st[pos] = ary[i];
            len = max(len, pos + 1);
            dl[i] = pos;
        }
        memset(st, 0, sizeof st);
        st[1] = ary[n - 1], len = 1;
        for (int i = n - 1; i >= 0; i--) {
            pos = lower_bound(st, st + len, ary[i]) - st;
            st[pos] = ary[i];
            len = max(len, pos + 1);
            dr[i] = pos;
        }
        int ans = 0;
        for (int i = 0; i < n; i++)
            ans = max(ans, 2 * min(dl[i], dr[i]) - 1);
        printf("%d\n", ans);
    }
}

附上模板

int LIS()
{
    memset(dp, 0, sizeof(int)*n);
    int len = 1;
    dp[0] = a[0];
    for (int i = 1; i < n; ++i)
    {
        int pos = lower_bound(dp, dp + len, a[i]) - dp; //pos 为当前位置的最大上升子序列的长度
        dp[pos] = a[i];
        len = max(len, pos + 1);
    }
    return len;
}
BFS

CodeForces 295C Greg and Friends

Posted on

bfs + dp 好题。
真好,比赛的时候想不出来,看题解的时候感觉好复杂……
看完写的时候感觉非常流畅!

题意:
载人过岸,一艘船最大载重 k 已经给定。每个人的重量只会是50或者100。问最小的过岸次数与方案数。

思路:
老实说这个题目我可以看就知道是道搜索题,因为和那个什么东西(就是搜索入门的那个)来着非常像。
最重要的还是理清状态与思路。
以左岸50重人数,100重人数,船是否在左岸表示一个状态,对他进行 bfs ,只要满足船重量大于 0 并且小于等于最大 k,每次过岸花费 1 。第一个搜索到 最终状态的就是我们要求的结果。

而我们的方案数,只能通过dp来球,dp最讲求的就是状态,

转移方程如下:

如果是 左岸 -- > 右岸 anum表示 50重总人数 , bnum 表示 100重 总人数

dp[x][y][0] += dp[a][b][1] \times C_a^{a-x} \times  C_b^{b-y}

否则

dp[x][y][1] += dp[a][b][0]  \times C_{anum-a}^{x-a} \times  C_{bnum-b}^{y-b}

写到中间的时候突然发现组合数求不来……尴尬……百度了一下,在数据较小的时候可以直接递推求

C_n^m = C_n^{m-1} + C_{n-1}^{m-1}

AC Code

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int maxn = 55;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;

int n, k;
int anum, bnum, maxa, maxb;
ll dp[maxn][maxn][2], c[maxn][maxn], dis[maxn][maxn][2];

struct status {
    int an;
    int bn;
    int isLeft;
    status() {}
    status(int _an, int _bn, int _isLeft)
        : an(_an)
        , bn(_bn)
        , isLeft(_isLeft)
    {
    }
};

queue<status> que;

int bfs()
{
    c[0][0] = 1;
    for (int i = 1; i <= 50; i++) {
        c[i][0] = 1;
        for (int j = 1; j <= i; ++j)
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
    }
    maxa = anum > 0 ? k / anum : 0, maxb = bnum > 0 ? k / bnum : 0;
    que.push(status(anum, bnum, 1));
    dis[anum][bnum][1] = 0;
    dp[anum][bnum][1] = 1;
    status now, nxt;
    while (!que.empty()) {
        now = que.front();
        que.pop();
        if (!now.an && !now.bn && !now.isLeft)
            return dis[0][0][0];
        for (int i = 0; i <= maxb; i++)
            for (int j = i ? 0 : 1; j <= maxa; j++) {
                if (i * 100 + j * 50 > k)
                    break;
                if (now.isLeft) {
                    if (now.an - j < 0 || now.bn - i < 0)
                        continue;
                    nxt.an = now.an - j, nxt.bn = now.bn - i, nxt.isLeft = false;
                    (dp[nxt.an][nxt.bn][0] += dp[now.an][now.bn][1] * c[now.an][j] % mod * c[now.bn][i] % mod) %= mod;
                    if (!dis[nxt.an][nxt.bn][0]) {
                        dis[nxt.an][nxt.bn][0] = dis[now.an][now.bn][1] + 1;
                        que.push(nxt);
                    }
                } else {
                    if (now.an + j > anum || now.bn + i > bnum)
                        continue;
                    nxt.an = now.an + j, nxt.bn = now.bn + i, nxt.isLeft = true;
                    (dp[nxt.an][nxt.bn][1] += dp[now.an][now.bn][0] * c[anum - now.an][j] % mod * c[bnum - now.bn][i] % mod) %= mod;
                    if (!dis[nxt.an][nxt.bn][1]) {
                        dis[nxt.an][nxt.bn][1] = dis[now.an][now.bn][0] + 1;
                        que.push(nxt);
                    }
                }
            }
    }
    return -1;
}

int main()
{
    int weight;
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%d", &weight);
        if (weight == 50)
            anum++;
        else
            bnum++;
    }
    int step = bfs();
    if (step == -1) {
        puts("-1\n0");
    } else
        printf("%d\n%lld\n", step, dp[0][0][0]);
    return 0;
}

递推

CodeForces 173C Spiral Maximum

Posted on

真是天真了,在计算器上计算复杂度在 1e8 ,给了 3s 时间以为侥幸能过,就用暴力写了……
结果拖到最后也没有写出来……

传送门

题意:
计算最大的有空行的弓形矩阵值。

思路:
如果说你观察仔细的话,你会发现 5×5 方阵 与 3×3 的方阵 差一个格子互补, 7×7 的 方阵 与 5×5 的方阵 差一个格子互补, 9×9 的 方阵 与7× 7 的方阵 差一个格子互补……

那么我们先预处理好每一个 3×3 方阵的值,再通过递推就能知道每一个方阵的值了

AC Code

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(num, ary) memset((ary), (num), sizeof((ary)))

using namespace std;
const int maxn = 550;
const int inf = 0x3f3f3f3f;

int n, m, ans;
int mat[maxn][maxn];
int dp[maxn][maxn][2];
int sum[maxn][maxn];

inline int recSum(int x1, int y1, int x2, int y2)
{
    return sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
}

inline void prepSum()
{
    ans = -inf;
    range(i, 1, n)
        range(j, 1, m)
            sum[i][j] = mat[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
}

inline int solve(int x, int y, int len)
{
    if (len == 0)
        return dp[x][y][0] = mat[x][y];
    else {
        dp[x][y][0] = recSum(x, y, x + len, y + len);
        dp[x][y][0] -= mat[x + 1][y];
        dp[x][y][0] -= dp[x + 1][y + 1][1];
        return dp[x][y][0];
    }
}

int main()
{
    scanf("%d %d", &n, &m);
    range(i, 1, n)
        range(j, 1, m)
            scanf("%d", &mat[i][j]);
    prepSum();
    range(k, 0, min(n, m))
    {
        rrange(i, 1, n)
            rrange(j, 1, m)
                dp[i][j][1] = dp[i][j][0];
        rrange(i, 1, n)
        {
            if (i + k > n)
                continue;
            rrange(j, 1, m)
            {
                if (j + k > m)
                    continue;
                int p = solve(i, j, k);
                if (k > 0)
                    ans = max(ans, p);
            }
        }
        k++;
    }
    printf("%d\n", ans);
    return 0;
}
树形DP

HDU4118 这也算树形DP?

Posted on

传送门

题意:

给你一个无向图,保证联通并且没有环(实质上就是一棵树……),要求:
每个点移动到另一个点去,并且不可能会有两个点移动到同一个点去,求最大移动距离和。

思路:

队友告诉我是图论……
…………
然后我特么还信了……
……………………

在看到结点个数达到 1e5 的时候我就应该意识到,基本不会是什么图论算法了。

我们可以这么想,先只考虑一半的节点移动到另一半的节点。
再是我们得确认一点,假如我可以得到这棵树的重心,那么重心一边的节点必然得移动到重心另一边的节点去才能使得移动距离和最大。(这个是显然的吧……举个例子 a-b-c-d a->c 必然会比 a->b 距离和大,而且,a->b影响的是 a,b 两个节点。)
然而我们无法轻松找到一棵树的重心,但是,我们从每一条边进行考虑,要使移动距离和最大,由该边断开形成的两棵子树,节点数目小的那一棵必然会全部移动到结点数目更多的那一棵,因为树的重心必然在节点数目更多的那一棵子树上,而且反过来移动也是不可能的吧…………

于是我们只要一次dfs就好了……

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 5;

int n, idx;
int head[maxn];
int node_num[maxn];
long long ans;

struct node {
    int to;
    int dis;
    int nxt;
} edges[maxn << 1];

void addEdge(int u, int v, int w)
{
    edges[idx].to = v;
    edges[idx].dis = w;
    edges[idx].nxt = head[u];
    head[u] = idx++;
}

void init()
{
    for (int i = 0; i <= n; i++) {
        head[i] = -1;
        node_num[i] = 0;
    }
    idx = 0;
    ans = 0;
}

int tree_dp(int cur, int pre)
{
    int total = 1, v, tmp;
    for (int it = head[cur]; ~it; it = edges[it].nxt) {
        v = edges[it].to;
        if (v != pre) {
            tmp = tree_dp(v, cur);
            ans += min(tmp, n - tmp) * edges[it].dis * 2; //因为来回,所以乘2
            total += tmp;
        }
    }
    return total;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int T, u, v, w;
    cin >> T;
    for (int cas = 1; cas <= T; cas++) {
        cin >> n;
        init();
        for (int i = 1; i < n; i++) {
            cin >> u >> v >> w;
            addEdge(u, v, w);
            addEdge(v, u, w);
        }
        tree_dp(1, -1);
        printf("Case #%d: %lld\n", cas, ans);
    }
    return 0;
}

很多题解都说是 树形DP ,为什么我指示觉得就是一个 DFS …… ~~虽然很有我之前学得模板风格~~

顺带一提的是,网上的题解质量真是越來越差了,很多核心部分的代码,直接一个显然得就没了……然后没多大卵用的东西瞎扯一堆……

树形DP

树形DP入门(持续更新中

Posted on
以前在暑假集训的时候搞得最多的还是图论相关,如果碰到树形结果很多时候就直接用搜……当然绝大多数时候也都T了……(当时也不喜欢分析复杂度,真是个坏习惯……
  

树形DP,简单说还是在树上做决策,只要把基础DP掌握好了我想应该不会是什么难事,只是换个场地罢了……

0. 入门题 POJ 2342

题意:
某公司要举办一次晚会,但是为了使得晚会的气氛更加活跃,每个参加晚会的人都不希望在晚会中见到他的直接上司,现在已知每个人的活跃指数和上司关系(当然不可能存在环),求邀请哪些人(多少人)来能使得晚会的总活跃指数最大。

思路:
定义数组dp[maxn][2],dp[k][0]表示第 k 人不去,dp[k][1] 表示第 k 人去。定义 son 为第 K 人的某个下属
我们从下往上分析,对于第 K 个人有以下去与不去两种情况

  • 假如 K 参加,那么对于他的每一个下属都不会去,那么就只能加上这个下属不去的这棵子树的值 dp[son][0]
  • 假如 K 不参加,那么他的下属可以选择去或者不去,当然我们要选择子树权值最大的 max(dp[son][0],dp[son][1])
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define ll long long

using namespace std;

const int maxn = 10000;

vector<int> tree[maxn];
int n;
int dp[maxn][2];

void tree_dp(int cur, int pre)
{
    int sz = tree[cur].size();
    for (int i = 0; i < sz; i++) {
        int son = tree[cur][i];
        if (son != pre) {
            tree_dp(son, cur);
            dp[cur][1] += dp[son][0];
            dp[cur][0] += max(dp[son][0], dp[son][1]);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int u, v;
    while (cin >> n) {
        for (int i = 1; i <= n; i++) {
            cin >> dp[i][1];
            tree[i].clear();
            dp[i][0] = 0;
        }
        while (cin >> u >> v) {
            if (u == 0 && v == 0)
                break;
            tree[u].push_back(v);
            tree[v].push_back(u);
        }
        tree_dp(1, -1);
        printf("%d\n", max(dp[1][0], dp[1][1]));
    }
    return 0;
}

顺便值得一提的是:
我看了很多网上的题解,无一都选择先找到树的根节点,然后从根节点进行向下dp。这样或许可以降低复杂度
~~因为出数据都习惯把初始树建的平衡一些……~~
但对于一棵树来说,无论你把哪一个节点定为根节点,它都能转化成另外一棵树,在这里是没有什么影响的。更何况,极端数据不排除会有极度不平衡的情况,其结果是一样的,该A的A,该WA的WA……还不如偷懒一点,提升一点码速。

1.1 向下递推 POJ 1947 Rebuilding Roads

题意:
给一棵树,问最少删掉几条边.使得剩下的子树中有节点个数为p个。

思路:
定义数组 dp[root][n] 表示以 当前节点为 root 节点,含有 n 个点所需删除的最小边数。
显然 dp[root][1]=root节点的所有孩子的个数+1(一个父亲节点),但是对于一棵树的根节点是没有父亲节点的。我这里先不考虑父亲节点,到最后再加上去。

初始状态已经确定,关键的还是 转移方程

dp[root][n] = min(dp[root][n],dp[root][n-k]+dp[root.son][k]-1);

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define ll long long

using namespace std;

const int maxn = 160;
int n, p, ans;
vector<int> key[maxn];
int dp[maxn][maxn];

int tree_dp(int root)
{
    int total = 1, sz = key[root].size();
    for (int i = 0; i < sz; i++)
        total += tree_dp(key[root][i]);
    dp[root][1] = sz;
    for (int j = 0; j < sz; j++) {
        int son = key[root][j];
        for (int i = min(p, total); i > 1; i--) {
            for (int k = 1; k < i; k++) {
                dp[root][i] = min(dp[root][i], dp[root][i - k] + dp[son][k] - 1);
            }
        }
    }
    ans = min(ans, dp[root][p] + (root != 1));
    return total;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int u, v;
    while (cin >> n >> p) {
        for (int i = 1; i <= n; i++)
            key[i].clear();
        memset(dp, 0x3f, sizeof dp);
        for (int i = 1; i < n; i++) {
            cin >> u >> v;
            key[u].push_back(v);
        }
        ans = 0x3f3f3f3f;
        tree_dp(1);
        cout << ans << endl;
    }
    return 0;
}
1.2 树上的01背包 HDU 1561

题意:
给你一个森林,每个节点都赋予一个权值。让你取 m 个节点,使得节点和最大。
当然,取节点也是有条件的: 如果你要取走这个节点,那你必须先取走它的父亲节点。

思路:
额外增加一个超级根节点,让这片森林里的每棵树的根节点都成为这个超级根节点的孩子,以形成一棵树。
再与上题一样,在树上不断向下递推即可

转移方程: dp[root][i] = max( dp[root][i] , dp[root][i-k] + dp[root.son][k])

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#define ll long long

using namespace std;

const int maxn = 205;
int n, idx, ans, m;
int head[maxn], dp[maxn][maxn], val[maxn];

struct edge {
    int to;
    int nxt;
} edges[maxn << 1];

void addEdge(int u, int v)
{
    edges[idx].to = v;
    edges[idx].nxt = head[u];
    head[u] = idx++;
}

void init()
{
    for (int i = 0; i <= n; i++) {
        head[i] = -1;
        for (int j = 0; j <= n; j++)
            dp[i][j] = 0;
    }
    idx = val[0] = 0;
    m++;
}

void treeDP(int root)
{
    dp[root][1] = val[root];
    for (int it = head[root]; ~it; it = edges[it].nxt) {
        int v = edges[it].to;
        treeDP(v);
        for (int i = m; i >= 1; i--)
            for (int k = 1; k < i; k++)
                dp[root][i] = max(dp[root][i], dp[root][i - k] + dp[v][k]);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int u;
    while (cin >> n >> m) {
        if (n == 0 && m == 0)
            break;
        init();
        for (int i = 1; i <= n; i++) {
            cin >> u >> val[i];
            addEdge(u, i);
        }
        treeDP(0);
        cout << dp[0][m] << endl;
    }
    return 0;
}
1.3 树上的最大连续序列 POJ 1192

题意:
题目虽然是中文,但说的非常繁琐。
简单概括就是 给定一个平面整点集,点与点间在|x1-x2| + |y1-y2| = 1 时两点连通,且形成的图没有回路~~其实就是一棵树啦~~,每个点有一个可正可负的权值,求最大权和连通子图。

思路:
和一维的 求连续最大权值序列 是一个思路

转移方程: dp = max(dp, dp + son )

//好激动呀,这是第一道我自己独立写出来的树形DP

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <stack>
#include <vector>
#define ll long long

using namespace std;

const int maxn = 1005;
int n, idx, ans;
int head[maxn];

struct node {
    int x, y, w;
} nodes[maxn];

struct edge {
    int to;
    int nxt;
} edges[maxn << 1];

void addEdge(int u, int v)
{
    edges[idx].to = v;
    edges[idx].nxt = head[u];
    head[u] = idx++;
}

bool judgeAdj(int u, int v)
{
    return abs(nodes[u].x - nodes[v].x) + abs(nodes[u].y - nodes[v].y) == 1;
}

void init()
{
    for (int i = 0; i <= n; i++)
        head[i] = -1;
    idx = ans = 0;
}

int treeDP(int cur, int pre)
{
    int dp = nodes[cur].w;
    for (int it = head[cur]; it != -1; it = edges[it].nxt)
        if (edges[it].to != pre) 
            dp = max(dp, dp + treeDP(edges[it].to, cur));
    return dp;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    while (cin >> n) {
        init();
        for (int i = 0; i < n; i++)
            cin >> nodes[i].x >> nodes[i].y >> nodes[i].w;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) {
                if (judgeAdj(i, j)) {
                    addEdge(i, j);
                    addEdge(j, i);
                }
            }
        ans = treeDP(1, -1);
        cout << ans << endl;
    }
    return 0;
}