G - FATE

题意：
xhd升掉最后一级还需n的经验值，xhd还留有m的忍耐度，每杀一个怪xhd会得到相应的经验，并减掉相应的忍耐度。当忍耐度降到0或者0以下时，xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能升掉这最后一级吗？
题解：
dp[i][j]表示杀i只怪不超过j忍耐度时获得的最大经验值，完全背包模板。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int main()
{
    int dp[105][105];
    int n, m, k, s, v[105], c[105], ans;
    while (cin >> n >> m >> k >> s)
    {
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < k; i++)
            cin >> v[i] >> c[i];
        for (int i = 0; i < k; i++)
            for (int j = 1; j <= s; j++)
                for (int l = c[i]; l <= m; l++)
                    dp[j][l] = max(dp[j - 1][l - c[i]] + v[i], dp[j][l]);
        ans = -1;
        for (int i = 0; i <= m; i++)
            if (dp[s][i] >= n)
            {
                ans = m - i; 
                break;
            }
        cout << ans << endl;
        }
}

H - Partial Tree

题意：
构造一棵树使得这棵树的价值最大。树的价值等于节点价值的和，节点的价值等于度数i的函数f(i)。
题解：
转化为完全背包，背包的容量为2n−2，我们要恰好选n个物品而且要恰好装满背包。体积为i的物品的价值为f(i)，而且每种物品有无穷多个。所以可以设计出类似的状态：d(i,j)表示选了i件物品，体积为j时所能得到的最大价值。

#include <cstring>
#include <algorithm>
#include<iostream>
using namespace std;
const int maxn = 2050;
int n;
int f[maxn];
int d[2][maxn];
int main()
{
    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i < n; i++)
            cin >> f[i];
        memset(d, 0, sizeof(d));
        int cur = 1;
        d[1][0] = n * f[1];
        for (int i = 2; i <= n - 1; i++) {
            cur ^= 1;
            memset(d[cur], 0, sizeof(d[cur]));
            for (int j = 0; j < i - 1; j++)
                d[cur][j] = d[cur ^ 1][j];
            for (int j = i - 1; j <= n - 2; j++)
                d[cur][j] = max(d[cur ^ 1][j], d[cur][j - i + 1] + f[i] - f[1]);
        }
        cout << d[cur][n - 2] << endl;
    }
    return 0;
}