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

tag:
动态规划，贪心，背包DP

思路：
用 f[k][i][j] 来表示前k块木板能否组成三角形。所以状态转移方程为：
f[k][i][j] = f[k - 1][i - a[k]][j] || f[k - 1][i][j - a[k]] || f[k][i][j]
因为转移时只跟 f[k - 1][][] 层的数据有关，所以可以用类似01背包问题的方式来简化掉这一维。初始化 f[0][0] = 1 之后对于每一个可能的结果判断是否为合法三角形，然后计算面积更新最大值即可。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 50;
int n, sum;
int a[N];
bool f[N * N][N * N];
long long ans;
bool check(int a, int b, int c)
{
    return a + b > c && a + c > b && b + c > a;
}
double resolue(int a, int b, int c)
{
    double p = (a * 1.0 + b + c) / 2;
    return sqrt(p * (p - a) * (p - b) * (p - c));
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        sum += a[i];
    }
    f[0][0] = 1;
    for (int k = 1; k <= n; k ++)
        for (int i = sum / 2; i >= 0; i --)
            for (int j = sum / 2; j >= 0; j --)
            {
                if (i - a[k] >= 0 && f[i - a[k]][j]) f[i][j] = 1;
                if (j - a[k] >= 0 && f[i][j - a[k]]) f[i][j] = 1;
            }
    double res = -1;
    for (int i = sum / 2; i > 0; i --)
        for (int j = sum / 2; j > 0; j --)
        {
            if (!f[i][j]) continue;
            if (!check(i, j, sum - i - j)) continue;
            res = max(res, resolue(i, j, sum - i - j));
        }
    if (res == -1) cout << -1 << endl;
    else cout << (long long)(res * 100) << endl;
    return 0;
}

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

tag:
动态规划，位运算

思路：
如果用求最长上升子序列的方式来求会超时。这时我们可以观察到因为要满足b_i & b_{i - 1} != 0，所以对于以a_i 结尾的数来说，只要是某一个序列末尾的数的某一位和a_i 都是1就可以想接。所以可以用一个数列bit来存某一位为1时的最长序列。之后更新时只需要枚举a_i 的每一位为1的情况，更新f就行。最后求出最大值后，用这个最大值再来更新当前情况下的bit数组值。对于枚举每一位可以通过lowbit函数求出最低位的1（2^k 的形式），之后再通过map log_2来映射每一个2^k 的 k值即为位数。

代码：

#include <iostream>
#include <map>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int n;
int ans;
int f[N];
int bit[N];
map<int, int> log_2;
int lowbit(int x)
{
    return x & -x;
}
int main()
{
    cin >> n;
    for (int i = 0, j = 1; i <= 31; i ++, j <<= 1)
    {
        log_2[j] = i;
    }
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = 1; i <= n; i ++)
    {
        for (int j = a[i], low = lowbit(j); j; j -= low, low = lowbit(j))
        {
            f[i] = max(f[i], bit[log_2[low]] + 1);
        }
        for (int j = a[i], low = lowbit(j); j; j -= low, low = lowbit(j))
        {
            bit[log_2[low]] = max(bit[log_2[low]], f[i]);
        }
        ans = max(ans, f[i]);
    }
    cout << ans << endl;
    return 0;
}

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

tag：
树形DP，动态规划

思路：
用数组f[u, j] 表示以u为根节点使用不超过 j 条边时最大的苹果数量。和背包问题有点不同的是，对于每一个点来说，假如需要用到某一个子节点来更新，则需要与之想连，所以其实是需要预备那个子节点所连的所有边 + 1的边来更新。所以状态转移方程为 f[u, j] = max(f[u, j], f[u, j - k - 1] + f[v,k] + w).在用二维循环更新时，不能让可能用到的边超过子树拥有的边，所以每次dfs之后还需要用s数组来更新以当前节点为根时所拥有的最大的边数。

代码：

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