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

tag:
动态规划，区间DP，2010

思路：
利用区间DP来做。设 f[i][j][0] 表示区间i到j中i从左边进入区间的情况， f[i][j][1] 表示区间i到j中j从右边进入区间的情况。当i从左边进去时，上一个区间应该是 i + 1 到 j ，所以只有当 h[i] < h[i + 1] 以及 h[i] < h[j] 时才能更新。同理当 h[j] > h[i] 以及 h[j] > h[j - 1] 时，j从右边进入区间，区间从 i 到 j - 1 更新到 i 到 j 。初始化为了避免当一个数字时有两种情况，所以可以是都假装是从左边进入区间，（或者是右边也行只要保证只保留一种情况就行）。最后答案将 f[1][n][0] 和 f[1][n][1] 两种情况相加后取模输出即可。

代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1010, mod = 19650827;
typedef long long LL;
int n;
int h[N];
LL f[N][N][2];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> h[i];
    for (int i = 1; i <= n; i ++) f[i][i][0] = 1;
    for (int len = 1; len <= n; len ++)
    {
        for (int i = 1, j = i + len; j <= n; i ++, j ++)
        {
            if (h[i] < h[i + 1]) f[i][j][0] += f[i + 1][j][0];
            if (h[i] < h[j]) f[i][j][0] += f[i + 1][j][1];
            if (h[j] > h[i]) f[i][j][1] += f[i][j - 1][0];
            if (h[j] > h[j - 1]) f[i][j][1] += f[i][j - 1][1];
            f[i][j][0] %= mod;
            f[i][j][1] %= mod;
        }
    }
    LL res = (f[1][n][0] + f[1][n][1]) % mod;
    cout << res << endl;
    return 0;
}

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;
}