思路

这是一道非常经典的树形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;
}

思路

一看这道题就知道是划分车辆的DP。一开始想的是F[前i辆车][划分次数j]=前i辆车划分j次的时间，然后发现这种写法很慢，而且在本题中没有说明划分的次数，我们只需要求前n辆车的解即可。

转移方程：F[i] = F[j-1] + L / (lowest_spd in [1,j])，转移条件是不超载的情况下。

这题比较毒瘤，int会被卡，double的无穷大必须要真·无穷大。

代码

// P1594.cpp
#include <iostream>
#include <iomanip>

using namespace std;

#define ll long long
const double INF = 9223372036854775807ll;
const ll maxn = 1100;
struct car
{
    double v, w;
} cars[maxn];
double W, L, N;
double F[maxn];

void DP()
{
    F[0] = 0;
    for (ll i = 1; i <= N; i++)
    {
        F[i] = (double)INF;
        double load = 0;
        double lspd = INF;
        for (ll j = i; j > 0; j--)
        {
            load += cars[j].w;
            if (load > W)
                break;
            lspd = min(lspd, cars[j].v);
            F[i] = min(F[i], F[j - 1] + L / lspd);
        }
    }
}

int main()
{
    cin >> W >> L >> N;
    for (ll i = 1; i <= N; i++)
        cin >> cars[i].w >> cars[i].v;
    DP();
    cout << fixed << setprecision(1) << F[(ll)N] * 60;
    return 0;
}