思路

一开始我还以为是拓扑排序，后面写代码的时候仔细思考了这道题，应该是树形dp。

主要的思路就是做一个编号为0的虚拟节点（这个点权重（学分）为0），然后建一棵树。构造dp方程\(F[u][size] = F[son][subsize] + F[u][size – subsize]\)。其中这里需要注意的是，这个本质上是一个树形的01背包，所以在生成dp表的时候需要反着推。（坑了我一个小时，哎我还是太菜了）输出的时候因为有点0的存在所以背包容量会比之前的大一个单位。

还需要注意的是，在我的代码中，我用了一个dfss来计算每个子背包的容量，不知道有没有必要，希望大佬能指出是否有这个必要。

代码

// P2014.cpp
#include <iostream>
#include <queue>
using namespace std;

const int maxn = 2100;
struct edge
{
    int to, next;
} edges[maxn << 1];
int deg[maxn];
int indeg[maxn];
int head[maxn];
int weight[maxn];
int current = 0;

int n, m;

void addpath(int src, int dst)
{
    edges[current].to = dst;
    edges[current].next = head[src];
    head[src] = current++;
}

int F[maxn][maxn];
int sizes[maxn];

void dfss(int u)
{
    sizes[u] = 1;
    for (int i = head[u]; i != -1; i = edges[i].next)
    {
        dfss(edges[i].to);
        sizes[u] += sizes[edges[i].to];
    }
}

void dfs(int u)
{
    for (int i = 1; i <= m; i++)
        F[u][i] = weight[u];
    for (int i = head[u]; i != -1; i = edges[i].next)
    {
        dfs(edges[i].to);
        int jto = edges[i].to;
        for (int len = m + 1; len >= 2; len--)
            for (int lens = 0; lens < len; lens++)
                F[u][len] = max(F[u][len], F[u][len - lens] + F[jto][lens]);
    }
}

int main()
{
    fill(head, head + maxn, -1);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        int k, s;
        cin >> k >> s;
        weight[i] = s;
        addpath(k, i), indeg[i]++, deg[k]++;
    }
    dfss(0);
    dfs(0);
    cout << F[0][m + 1];
    return 0;
}

思路

这是一道非常经典的树形DP，题中直接讲到这是树形结构。建树之后，状态转移方程不难想出：

• 对于每一个点，F[u][0]代表不选这个点的最优解，F[u][1]代表选这个点的最优解。
• 对于运行时的每个点，都有F[u][1] = happiness[u]。
• 对于一个点的孩子遍历，都有F[u][0] += max(F[v][1], F[v][0])，F[u][1] += F[v][0]。

由此，我们可以轻松的写出下列的代码。

代码

// P1352.cpp
#include <iostream>

using namespace std;
// Data Structure;
const int maxn = 6100;
int n;
int R[maxn];
// Graph stuff;
// Notice: the edge space should be doubled;
struct edge
{
    int to, next;
} edges[maxn << 1];
int head[maxn];
int current = 0;
int F[maxn][2];
int deg[maxn];
// DFS func;
void DFS(int curt)
{
    // Initalize the DP Table;
    F[curt][1] = R[curt];
    // Find the subnodes;
    for (int i = head[curt]; i != -1; i = edges[i].next)
    {
        // Call the subtree to be ready;
        DFS(edges[i].to);
        // Deciding;
        F[curt][1] += F[edges[i].to][0];
        F[curt][0] += max(F[edges[i].to][0], F[edges[i].to][1]);
    }
}

void add_path(int src, int dst)
{
    edges[current].to = dst;
    edges[current].next = head[src];
    head[src] = current++;
}

int main()
{
    // Initialize;
    cin >> n;
    fill(head, head + maxn, -1);
    for (int i = 1; i <= n; i++)
        cin >> R[i];
    int a, b;
    for (int i = 1; i <= n - 1; i++)
    {
        cin >> a >> b, add_path(b, a);
        deg[a]++;
    }
    cin >> a >> b;
    // Find the root node by the degrees saved before;
    int root = 0;
    for (int i = 1; i <= n; i++)
        if (deg[i] == 0)
        {
            root = i;
            break;
        }
    // Start to dp;
    DFS(root);
    // Output;
    cout << max(F[root][0], F[root][1]);
    return 0;
}

思路

本题数据很大，如果用传统的路径DP数组开不下，然而我们可以对距离进行取模：取模之后，当青蛙在跳的时候，该跳到的总会跳到，跳不到的总会挑不到（类比基本博弈论的内容）。这下我们压缩路径之后就可以进行正常的DP了。

其他细节（细节太多了）见代码。

代码

// P1052.cpp
#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 400000;
const int maxm = 1000;
const int INF = 0x7fffffff;
// positions of stones;
int stone[maxm];
// used for DP;
int F[maxn];
// the distance between 2 stones;
int diff[maxn];
// flag[pos] to indicate whether there is a stone at pos;
bool flag[maxn];
int L, S, T, M;

void DP()
{
    // start loop to the farthest;
    for (int i = 1; i <= L + T; i++)
        for (int k = S; k <= T; k++)
        {
            // to transform from F[i-k];
            // k is the step number;
            if (i - k >= 0)
                F[i] = min(F[i], F[i - k]);
            // if there is a stone, count it!
            F[i] += (flag[i]) ? 1 : 0;
        }
}

int main()
{
    // input;
    cin >> L >> S >> T >> M;
    for (int i = 1; i <= M; i++)
        cin >> stone[i];
    sort(stone + 1, stone + M + 1);
    diff[0] = 0;
    // to calc and zip with the distances;
    for (int i = 1; i <= M; i++)
        diff[i] = (stone[i] - stone[i - 1]) % 2520;
    // to update the shortened distances and the flag[];
    for (int i = 1; i <= M; i++)
        stone[i] = stone[i - 1] + diff[i], flag[stone[i]] = true;
    L = stone[M];
    // to init for the F;
    for (int i = 0; i <= L + T; i++)
        F[i] = M;
    F[0] = 0;
    // Start to DP();
    DP();
    // to figure out the ans;
    int ans = M;
    for (int i = L; i < L + T; i++)
        ans = min(ans, F[i]);
    // output;
    cout << ans;
    return 0;
}

思路

这题我写了一天才AC…太难受了。

考虑这是一道DP题。首先按垃圾到来的时间排序，之后再进行DP。在DP中，当我们第一次跳出坑时便找到答案。如果正常退出DP函数的话便说明无法跳出坑。这是我们只需要模拟一下就可以知道最长存活时间。

这题比较难理解（我太菜了），（面对题解）写了一天才写出来。

代码

// P1156.cpp
#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

// Constants;
const int maxn = 2000;
const int maxt = 20000;
const int INF = 0x7fffffff - 10;
// Data structures;
int D, G;
int dp[maxn][200];
struct garbage
{
    int t, f, h;
    // Comparing function for sorting.
    bool operator<(const garbage &g) const
    {
        return t < g.t;
    }
} gars[maxn];
// To indicate if the genDP() exit normally;
bool flag = false;

void genDP()
{
    // generate;
    for (int i = 0; i < G; i++)
        for (int j = 0; j <= D; j++)
        {
            // If cow died;
            if (dp[i][j] < 0)
                continue;
            // If the cow is able to get out;
            if (j + gars[i + 1].h >= D && dp[i][j] >= (gars[i + 1].t - gars[i].t))
            {
                cout << gars[i + 1].t;
                flag = true;
                return;
            }
            // Transform the status;
            if (dp[i][j] - (gars[i + 1].t - gars[i].t) >= 0)
                dp[i + 1][j + gars[i + 1].h] = dp[i][j] - (gars[i + 1].t - gars[i].t);
            if (dp[i][j] - (gars[i + 1].t - gars[i].t) >= 0)
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + gars[i + 1].f - (gars[i + 1].t - gars[i].t));
        }
}
// The main func;
int main()
{
    // Prep for data;
    cin >> D >> G;
    gars[0].t = gars[0].f = gars[0].h = 0;
    for (int i = 1; i <= G; i++)
        cin >> gars[i].t >> gars[i].f >> gars[i].h;
    sort(gars + 1, gars + G + 1);
    fill(dp[0], dp[0] + maxn * 200, -INF);
    // The startup value of the health is 10;
    dp[0][0] = 10;
    genDP();
    if (flag)
        return 0;
    // If the genDP() exit abnormally:
    int m = 10;
    int acc = 0;
    for (int i = 1; i <= G; i++)
    {
        if (gars[i].t - gars[i - 1].t > m)
        {
            cout << m + acc;
            return 0;
        }
        acc += gars[i].t - gars[i - 1].t;
        m -= gars[i].t - gars[i - 1].t;
        m += gars[i].f;
    }
    // output;
    cout << acc + m;
    return 0;
}