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

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

tag:
动态规划，排序，背包DP

思路：
对于每一个垃圾来说，为了不去处理时间，可以按照时间顺序排列，之后只要关注两个属性，一个是高度，一个是时间。定义 f 数组，表示当前高度下生存的时间。每次更新先是判断当前高度能否等到这个垃圾，然后判断如果堆起来能不能逃出去，能的话输出这个垃圾掉落的时间。不能的话计算堆上去时的高度的 f ，用max更新，因为有可能不同的垃圾堆出相同的高度，这个时候需要保留最大值，然后再更新如果吃了之后当前高度的生存时间。最后假如不能出逃，就输出 f[0] 表示当高度为0时的生存时间，也就是最长的生存时间。

代码：

#include <iostream>  
#include <cstdio>  
#include <algorithm>  
#include <cstring>  
using namespace std;  
const int N = 110;  
struct rb {  
    int t, h, w;  
    bool operator < (const rb &b)const  
    {  
        return t < b.t;  
    }  
}r[N];  
  
int d, n;  
int f[N];  
int main()  
{  
    cin >> d >> n;  
    for (int i = 1; i <= n; i ++)  
    {  
        cin >> r[i].t >> r[i].w >> r[i].h;  
    }  
    sort(r + 1, r + n + 1);  
    f[0] = 10;  
    for (int i = 1; i <= n; i ++)  
        for (int j = d; j >= 0; j --)  
        {  
            if (f[j] >= r[i].t)  
            {  
                if (j + r[i].h >= d)  
                {  
                    cout << r[i].t << endl;  
                    return 0;  
                }  
                f[j + r[i].h] = max(f[j], f[j + r[i].h]);  
                f[j] += r[i].w;  
            }  
        }  
    cout << f[0];  
    return 0;  
}

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

tag:
动态规划，背包，USACO， 2003

思路：
可以转化为01背包问题来做，因为每个奶牛都只有选和不选两种状态。对于背包问题，需要考虑三个属性，一个是背包容量，一个是体积，还有一个是价值。在这道题中，iq和eq是等价的属性，所以可以一个当作体积，另外一个当作价值。关于背包容量，这道题没有显式的提出，不过我们可以用数据范围的最大值作为背包容量的最大值。因为iq和eq都是有正有负，所以就可以选择将数组向右扩大400000.因为转移方程是 f[j] = max(f[j], f[j - c[i].iq] + c[i].eq) 二维转变为一维。当是负数的时候，实际上 j - c[i].iq 是增大的，为了避免更新的对未更新的产生影响，所以需要变成从小到大遍历。

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 440;
struct cow {
    int iq, eq;
}c[N];
int f[N * 1000 * 2];
int n;
int res;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> c[i].iq >> c[i].eq;
    }
    memset(f,-0x3f ,sizeof f);
    f[400000] = 0;
    for (int i = 1; i <= n; i ++)
    {
        if (c[i].iq >= 0)
        {
            for (int j = 800000; j >= c[i].iq; j --)
            {
                f[j] = max(f[j], f[j - c[i].iq] + c[i].eq);
            }
        }
        else
        {
            for (int j = 0; j <= 800000 + c[i].iq; j ++)
            {
                f[j] = max(f[j], f[j - c[i].iq] + c[i].eq);
            }
        }
    }
    for (int i = 400000; i <= 800000; i ++)
    {
        if (f[i] >= 0)
        res = max(res, f[i] + i - 400000);
    }
    cout << res << endl;
    return 0;
}

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

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

思路：
用树形DP来解决。定义数组 f[i][k] 表示以i为根节点且i涂的颜色为k时的方案数。然后根据k的不同分别更新即可。最后答案输出以1为根节点时3个颜色方案数之和（以其他节点为根节点也可以）。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int mod = 1e9 + 7;
int e[N * 2], ne[N * 2], h[N], idx;
int n, k;
int c[N];
LL f[N][4];
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a]= idx ++;
}
void dfs(int u, int fa)
{
    if (c[u]) f[u][c[u]] = 1;
    else
    {
        f[u][1] = f[u][2] = f[u][3] = 1;
    }
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        dfs(j, u);
        f[u][1] = f[u][1] * ((f[j][2] + f[j][3]) % mod) % mod;
        f[u][2] = f[u][2] * ((f[j][1] + f[j][3]) % mod) % mod;
        f[u][3] = f[u][3] * ((f[j][1] + f[j][2]) % mod) % mod;
    }
}
int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> k;
    for (int i = 0; i < n - 1; i ++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    for (int i = 0; i < k;  i++)
    {
        int a, b;
        cin >> a >> b;
        c[a] = b;
    }
    dfs(1, 0);
    LL res = 0;
    for (int i = 1; i <= 3; i ++) res = (res + f[1][i]) % mod;
    cout << res << endl;
    return 0;
}