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

tag:
动态规划，背包DP，进制，USACO，2006

思路：
可以用背包来做。用 f[i] 表示john付i块钱时最少的硬币数，用 g[i] 表示店主找零i块钱时最少的硬币数，对于f来说，因为硬币数量有限所以需要用多重背包来完成。而对于g来说因为硬币无限多，所以可以用完全背包。对于体积上限取多少可以参考： https://www.luogu.com.cn/article/sd0bx6un

代码：

#include <iostream>  
#include <cstring>  
#include <cstdio>  
#include <algorithm>  
using namespace std;  
typedef long long LL;  
const int N = 10010, M = 150;  
int c[M], v[M];  
int f[N + M * M], g[N + M * M];  
int n, t, mx, sum;  
int main()  
{  
    cin >> n >> t;  
    for (int i = 1; i <= n; i ++)  
    {  
        cin >> v[i];  
        mx = max(mx, v[i] * v[i]);  
    }  
    for (int i = 1; i <= n; i ++)  
    {  
        cin >> c[i];  
        sum += v[i] * c[i];  
    }  
    if (sum < t)  
    {  
        cout << -1 << endl;  
        return 0;  
    }  
    memset(f, 0x3f, sizeof f);  
    memset(g, 0x3f, sizeof g);  
    g[0] = 0;  
    f[0] = 0;  
    for (int i = 1; i <= n; i ++)  
        for (int j = v[i]; j <= mx; j ++)  
            g[j] = min(g[j], g[j - v[i]] + 1);  
    for (int i = 1; i <= n; i ++)  
    {  
        for (int j = 1; j <= c[i]; j *= 2)  
        {  
            for (int k = mx + t; k >= j * v[i]; k --)  
                f[k] = min(f[k], f[k - j * v[i]] + j);  
            c[i] -= j;  
        }  
        if (c[i])  
            for (int k = mx + t; k >= c[i] * v[i]; k --)  
                f[k] = min(f[k], f[k - c[i] * v[i]] + c[i]);  
    }  
    int res = 0x3f3f3f3f;  
    for (int i = t; i <= t + mx; i ++)  
        res = min(res, f[i] + g[i - t]);  
    cout << (res == 0x3f3f3f3f ? -1 : 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/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;
}

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

tag:
树形DP, USACO, 2012

思路：
用f[u,m] 表示以u为根节点，向下走出不超过m步时的权值，d[u, m] 表示以u为根节点，向上或向下走不超过m步时的权值。利用两次dfs分别求出f和d，最后输出每个节点作为根节点时的权值和即可。

代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int h[N], e[N * 2], ne[N * 2], idx;
int w[N];
int n, k;
LL f[N][25], d[N][25];
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}
void dfs(int u, int fa)
{
    for (int i = 0; i <= k; i ++) f[u][i] = w[u];
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j != fa)
        {
            dfs(j, u);
            for (int p = 1; p <= k; p ++)
            {
                f[u][p] += f[j][p - 1];
            }
        }
    }
}
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][1] += d[u][0];
        for (int p = 2; p <= k; p ++)
        {
            d[j][p] += d[u][p - 1] - f[j][p - 2];
        }
        dfs2(j, u);
    }
}
int main()
{
    cin >> n >> k;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n - 1; i ++)
    {
        int u, v;
        cin >> u >> v;
        add(u, v), add(v, u);
    }
    for (int i = 1; i <= n; i ++) cin >> w[i];
    dfs(1, 0);
    for (int i = 1; i <= n; i ++)
        for (int j = 0; j <= k; j ++)
            d[i][j] = f[i][j];
    dfs2(1, 0);
    for (int i = 1; i <= n; i ++) cout << d[i][k] << endl;
    return 0;
}