url: https://www.luogu.com.cn/problem/P2986

tag:
动态规划，树形DP，USACO，2010

思路：
可以参考 洛谷P3478 POI 2008 STA-Station 都是要求出当某一个节点为根时其他点到这个根的距离，我们可以用一次dfs来求出以任意选的一个节点作为根节点时的答案，比如选择节点1为根节点。然后再利用一次dfs来做节点转移的更新，求当其他节点做根节点时的答案，然后和全局答案做一个更新。最后输出这个答案即可。对于这道题，状态转移方程1是 f[u] += f[j] + w[i] * s[j]; 用f[i] 表示以i为根节点时其他节点到该点的不方便值。状态转移方程2是 d[j] = d[u] - s[j] * w[i] + (cnt - s[j]) * w[i]; 先做初始化让 d[1] = f[1] 然后自上到下更新。

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
int e[N * 2], ne[N * 2], h[N], w[N * 2], idx;
int n;
LL cnt, ans;
int c[N];
LL f[N];
LL s[N];
LL d[N];
void add(int a, int b, int cc)
{
    e[idx] = b;
    w[idx] = cc;
    ne[idx] = h[a];
    h[a] = idx ++;
}
void dfs1(int u, int fa)
{
    s[u] = c[u];
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        dfs1(j, u);
        s[u] += s[j];
        f[u] += f[j] + w[i] * s[j];
    }
}
void dfs2(int u, int fa)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        d[j] = d[u] - s[j] * w[i] + (cnt - s[j]) * w[i];
        ans = min(ans, d[j]);
        dfs2(j, u);
    }
}
int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++) cin >> c[i], cnt += c[i];
    for (int i = 0; i < n - 1; i ++)
    {
        int a, b, cc;
        cin >> a >> b >> cc;
        add(a, b, cc), add(b, a, cc);
    }
    dfs1(1, 0);
    d[1] = f[1];
    ans = d[1];
    dfs2(1, 0);
    cout << ans << endl;
    return 0;
}

url: https://www.luogu.com.cn/problem/P1040

tag:
动态规划，递归，枚举，区间DP，NOIP提高组，2003

思路：
使用区间dp的思路，令 f[i][j] 为节点i到节点j之间最大的加分，并用 root[i][j] 记录下这段区间的根节点。之后遍历每一种可能的区间，依据题目的公式更新数组f记录root最后得出结果输出 f[1][n] 即表示给定的二叉树tree的最高加分。然后再输出该情况时树的前序遍历即可。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 31;
int h[N], e[N * 2], ne[N * 2], idx;
int n;
LL f[N][N];
int root[N][N];
void print(int l ,int r)
{
    if (l > r) return;
    cout << root[l][r] << ' ';
    if (l == r) return;
    print(l, root[l][r] - 1),print(root[l][r] + 1, r);
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> f[i][i], root[i][i] = i;
    for (int len = 1; len <= n; len ++)
        for (int i = 1; i + len <= n; i ++)
        {
            int j = i + len;
            f[i][j] = f[i + 1][j] + f[i][i];
            root[i][j] = i;
            for (int k = i + 1; k <= j; k ++)
            {
                if (f[i][j] < f[i][k - 1] * f[k + 1][j] + f[k][k])
                {
                    f[i][j] = f[i][k - 1] * f[k + 1][j] + f[k][k];
                    root[i][j] = k;
                }
            }
        }
    cout << f[1][n] << endl;
    print(1, n);
    return 0;
}

url: https://www.luogu.com.cn/problem/P1282

tag:
动态规划，枚举，背包DP

思路：
用 f[i][j] 表示用前i块多米诺骨牌形成的差值为j时旋转次数。因为差值的范围是-5000-5000，所以数组加一个5000的偏移量。状态转移方程为 f[i][j + p] = min(f[i - 1][j - (a[i] - b[i]) + p], f[i - 1][j - (b[i] - a[i]) + p] + 1); 。 j - (a[i] - b[i]) + p 表示未加上第i块多米诺骨牌时的差值。上下旋转时，当前的差值会反过来，同时次数也要加一。最后求答案值，求绝对值从小到大第一个合法的值就是答案（正负都合法的话取一个最小值），表示差值最小时的旋转次数。

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1010, p = 5000;
int f[N][N * 6 * 2];
int a[N], b[N];
int n;
int main()
{
    memset(f, 0x3f, sizeof f);
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i] >> b[i];
    f[1][0 + p + a[1] - b[1]] = 0, f[1][0 + p + b[1] - a[1]] = 1;
    if (a[1] == b[1]) f[1][p] = 0;
    for (int i = 2; i <= n; i ++)
    {
        for (int j = -5000; j <= 5000; j ++)
        {
            f[i][j + p] = min(f[i - 1][j - (a[i] - b[i]) + p], f[i - 1][j - (b[i] - a[i]) + p] + 1);
        }
    }
    int res = 0x3f3f3f3f;
    for (int i = 0; i <= 5000; i ++)
    {
        if (f[n][i + p] <= 1000 || f[n][-i + p] <= 1000)
        {
            res = min(f[n][i + p], f[n][-i + p]);
            break;
        }
    }
    cout << res << endl;
    return 0;
}

url: https://www.luogu.com.cn/problem/P2014

tag:
动态规划，树形DP，CTSC/CTS，1997

思路：
和背包比较像，但是有一点区别的是对如果某个节点要选，也需要将其选不同数量节点的情况，分别更新，也就是说不知道每个点的“体积”是多少。因为要选一门课需要将其有依赖的课也选。所以需要从小更新到大。如果将0也算节点，那么整个结构会构成棵树，此时也需要让m ++，表示一共选m + 1个节点。最后输出 f[0][m] 表示选0时不超过m门课，最大的学分。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 400;
int n, m;
int h[N], e[N * 2], ne[N * 2], idx;
int s[N];
int f[N][N];
void add (int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

void dfs(int u)
{
    f[u][1] = s[u];
    for (int i = h[u]; ~i; i = ne[i])
        dfs(e[i]);
    for (int i = h[u]; ~i; i = ne[i])
        for (int j = m; j > 0; j --)
            for (int k = 0; k < j; k ++)
                f[u][j] = max(f[u][j], f[u][j - k] + f[e[i]][k]);
}
int main()
{
    cin >> n >> m;
    m ++;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++)
    {
        int a;
        cin >> a >> s[i];
        add(a, i);
    }
    dfs(0);
    cout << f[0][m] << endl;
    return 0;
}

url: https://www.luogu.com.cn/problem/P5322

tag:
动态规划，背包DP

思路：
读入的时候反着读，用 a[i][j] 来表示第i座城第j个人出的兵。然后对每座城中的s种出兵的方式排序，得到 a[i][j] 表示第i座城前j个出兵最多的人出的兵。然后用分组背包的方式，每一座城每种出兵数量，用那座城的每一个前k个玩家出兵数量来更新f。最后输出 f[m] 即可。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20020;
int f[N];
int a[200][200];
int n, m, s;
int main()
{
    cin >> s >> n >> m;
    for (int i = 1; i <= s; i ++)
        for (int j = 1; j <= n; j ++)
            cin >> a[j][i];
    for (int i = 1; i <= n; i ++)
        sort(a[i] + 1, a[i] + s + 1);
    for (int i = 1; i <= n; i ++)
        for (int j = m; j >= 0; j --)
            for (int k = 1; k <= s; k ++)
            {
                if (j > a[i][k] * 2)
                {
                    f[j] = max(f[j - a[i][k] * 2 - 1] + i * k, f[j]);
                }
            }
    cout << f[m] << endl;
    return 0;
}