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

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

思路：
多重背包问题为基础，做两次01背包，前一次后一次，之后对于每次询问的id就跳过那个id求可能的最大值。

代码：

#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <algorithm>  
using namespace std;  
typedef long long LL;  
const int N = 100010;  
struct node{  
    int id;LL s;  
}w[N], v[N];  
LL f1[N][1010], f2[N][1010];  
int idx, m, n;  
int main()  
{  
    cin >> n;  
    for (int i = 1; i <= n;  i++)  
    {  
        int cw, cv, c;  
        cin >> cw >> cv >> c;  
        int now = 1;  
        while (now <= c)  
        {  
            w[++idx].s = cw * now, v[idx].s = cv * now;  
            w[idx].id = i, v[idx].id = i;  
            c -= now, now *= 2;  
        }  
        if(c) {  
            w[++idx].s = cw * c, v[idx].s = cv * c;  
            w[idx].id = i, v[idx].id = i;  
        }  
    }  
    cin >> m;  
    n = idx;  
    for (int i = 1; i <= n; i ++)  
    {  
        for (int j = 0; j <= 1000; j ++) f1[i][j] = f1[i - 1][j];  
        for (int j = 1000; j >= w[i].s; j --)  
        {  
            f1[i][j] = max(f1[i][j], f1[i - 1][j - w[i].s] + v[i].s);  
        }  
    }  
    for (int i = n; i >= 1; i --)  
    {  
        for (int j = 0; j <= 1000; j ++) f2[i][j] = f2[i + 1][j];  
        for (int j = 1000; j >= w[i].s; j --)  
        {  
            f2[i][j] = max(f2[i][j], f2[i + 1][j - w[i].s] + v[i].s);  
        }  
    }  
    for (int k = 1; k <= m; k ++)  
    {  
        int cn, V;  
        cin >> cn >> V;  
        cn ++;  
        LL ans = 0;  
        int l = 0, r = 0;  
        while (w[l + 1].id < cn && l < n) ++ l;  
        r = l;  
        while (w[r + 1].id <= cn && r < n) ++ r;  
        for (int j = 0; j <= V; j++)  
        {  
            ans = max(ans, f1[l][j] + f2[r + 1][V - j]);  
        }  
        cout << ans << endl;  
    }  
    return 0;  
}

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/P4158

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

思路：
用 f[i][j] 表示前i块木板粉刷j次最多的正确次数。用 g[i][j][k] 表示第i块木板粉刷j次粉刷前k个格子时最多的正确次数。用 sum[i][j] 表示第i块木板，前j个格子中需要涂成蓝色的有几个。
所以可以知道状态转移方程为 f[i][j] = max(f[i][j], f[i - 1][j - k] + g[i][k][m]) ；
g[i][j][k] = max(g[i][j][k], g[i][j - 1][q] + max(sum[i][k] - sum[i][q], k - q - sum[i][k] + sum[i][q])) 最后遍历不同种粉刷次数中最多的粉刷格子数。

代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
int f[51][2550], sum[51][2550];
int g[51][2550][51];
int n, m, t;
char s[100];
int main()
{
    cin >> n >> m >> t;
    for (int i = 1; i <= n; i ++)
    {
        cin >> s;
        for (int j = 1; j <= m; j ++)
        {
            if (s[j - 1] == '1') sum[i][j] = sum[i][j - 1] + 1;
            else sum[i][j] = sum[i][j - 1];
        }
    }
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            for (int k = 1; k <= m; k ++)
                for (int q = j - 1; q < k; q ++)
                    g[i][j][k] = max(g[i][j][k], g[i][j - 1][q] + max(sum[i][k] - sum[i][q], k - q - sum[i][k] + sum[i][q]));
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= t; j ++)
            for (int k = 0; k <= min(j, m); k ++)
                f[i][j] = max(f[i][j], f[i - 1][j - k] + g[i][k][m]);
    int res = 0;
    for (int i = 1; i <= t; i ++) res = max(res, f[n][i]);
    cout << res << endl;

    return 0;
}

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

tag:
动态规划，树形DP，背包DP

思路：
用 f[u][j] 表示第u个节点选择j个用户时的盈利数。使用分组背包的思想。状态转移方程为
f[u][k] = max(f[u][k], f[u][k - l] + f[j][l] - w[i]) 其中w表示如果将节点j接入时的成本。最后因为是求不亏本时最多可以观看转播的用户数，所以从m开始向下循环，直到找到第一个盈利大于等于0的然后输出用户数即可。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 3030;
int h[N], e[N * 2], ne[N * 2], w[N * 2], idx;
int n, m;
int p[N];
int s[N];
int f[N][N];
void dfs(int u, int fa)
{
    if (u > n - m) f[u][1] = p[u], s[u] = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        dfs(j, u);
        s[u] += s[j];
        for (int k = m; k >= 0; k --)
        {
            for (int l = 1; l <= min(k, s[j]); l ++)
            {
                f[u][k] = max(f[u][k], f[u][k - l] + f[j][l] - w[i]);
            }
        }
    }
}
void add(int a, int b, int c)
{
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx ++;
}
int main()
{
    memset(h, -1, sizeof h);
    memset(f, -0x3f, sizeof f);
    cin >> n >> m;
    for (int i = 1; i <= n - m; i ++)
    {
        int k;
        cin >> k;
        for (int j = 0; j < k; j ++)
        {
            int a, b;
            cin >> a >> b;
            add(i, a, b), add(a, i, b);
        }
    }
    for (int i = n - m + 1; i <= n; i ++) cin >> p[i];
    for (int i = 1; i <= n; i ++) f[i][0] = 0;
    dfs(1, 0);
    for (int i = m; i >= 0; i --)
    {
        if (f[1][i] >= 0)
        {
            cout << i;
            break;
        }
    }
    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;
}