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