Kalorona

P1594:护卫队题解

思路

一看这道题就知道是划分车辆的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;
}

P1070:道路游戏题解

思路

经过长时间琢磨题解之后，我理解了dalao们的想法。这道题使用一维即可，但是O（n^3）的时间复杂度确实惊人。奈何我太菜了，只能理解这一种，那我也就只能来写写n^3的题解了。

转移方程：F[i] = max(F[i], F[i-k] + sum – cost[curt]，其中i表示当前的时间，k表示目前设置的机器人的步数，sum代表累积起来的金币，curt表示当前机器人的编号。其中当curt = 0时，curt需要被设置成n（环形特征）。答案储存在F[m]。

代码

// P1070.cpp
#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 2020;
int table[maxn][maxn];
int cost[maxn];
int F[maxn];
int n, m, p;

int main()
{
    cin >> n >> m >> p;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> table[i][j];
    for (int i = 1; i <= n; i++)
        cin >> cost[i];
    fill(F, F + maxn, -(1e9));
    F[0] = 0;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
        {
            int curt = j - 1;
            if (curt == 0)
                curt = n;
            int sum = table[curt][i];
            for (int k = 1; k <= p; k++)
            {
                if (i - k < 0)
                    break;
                F[i] = max(F[i], F[i - k] + sum - cost[curt]);
                curt--;
                if (curt == 0)
                    curt = n;
                sum += table[curt][i - k];
            }
        }
    cout << F[m];
    return 0;
}

P2279:「HNOI2003」消防局的设立题解

思路

题面中给出的数据结构很显然是一棵树，我们需要求能覆盖整棵树的最少的消防局数量。我们先按照要求输入，决定根节点（我这里是1号）之后按深度排序，从深度最深的节点开始检测。如果一个节点没有被覆盖，那么就覆盖他的爷爷节点，这样可以使覆盖面积最大，在覆盖时向两个方向扩散设置vis[i]标记。被标记过的点则跳过，没有被标记的点则把消防局设在爷爷处。由于我们的设置过程是按照深度由深到浅渐进，所以不会存在潜在的问题。

代码

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

const int maxn = 4040;

struct edge
{
    int to, next;
} edges[maxn];
int head[maxn];
int F[maxn];
stack<int> st;
bool vis[maxn];
int current = 0;
int n;

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

void BFS()
{
    queue<int> q;
    q.push(1);
    st.push(1);
    while (!q.empty())
    {
        int curt = q.front();
        q.pop();
        for (int i = head[curt]; i != -1; i = edges[i].next)
            if (edges[i].to != F[curt])
                st.push(edges[i].to), q.push(edges[i].to);
    }
}

void DFS(int p, int dep)
{
    if (dep > 2)
        return;
    vis[p] = true;
    for (int i = head[p]; i != -1; i = edges[i].next)
        DFS(edges[i].to, dep + 1);
}

int main()
{
    cin >> n;
    fill(head, head + maxn, -1);
    fill(vis, vis + maxn, false);
    int num = -1;
    for (int i = 2; i <= n; i++)
    {
        cin >> num;
        F[i] = num;
        addpath(num, i), addpath(i, num);
    }
    // going to solve;
    BFS();
    int ans = 0;
    while (!st.empty())
    {
        int curt = st.top();
        st.pop();
        if (!vis[curt] && ++ans)
            DFS(F[F[curt]], 0);
    }
    cout << ans;
    return 0;
}

P1137:旅行计划题解

思路

好久没有写拓扑排序了。今天看到这题看了半天，由题解可知是拓扑序DP。原理根据拓扑序来进行DP。由于每个点在DAG是不会回路的，所以我们只需一头往下走就好，用dp[x]记录点x可到达的地方。使用拓扑排序就会让DP时不会出现影响其他已计算过的节点。

代码

// P1137.cpp
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int maxn = 100010;
int points[maxn];
int to[2 * maxn];
int next[2 * maxn];
int indeg[maxn];
int res[maxn];
int dp[maxn];
int tot = 0;
int current = 0;
int n, m;

void add_edge(int a, int b)
{
    to[current] = b;
    next[current] = points[a];
    points[a] = current++;
}

void toposort()
{
    queue<int> waiting;
    for (int i = 1; i <= n; i++)
        if (indeg[i] == 0)
            waiting.push(i), res[tot++] = i;
    while (!waiting.empty())
    {
        int curt = waiting.front();
        waiting.pop();
        for (int edge = points[curt]; edge != -1; edge = next[edge])
        {
            indeg[to[edge]]--;
            if (indeg[to[edge]] == 0)
                waiting.push(to[edge]), res[tot++] = to[edge];
        }
    }
}

void DP()
{
    for (int i = 1; i <= n; i++)
        dp[i] = 1;
    for (int i = 0; i < n; i++)
        for (int edge = points[res[i]]; edge != -1; edge = next[edge])
            dp[to[edge]] = max(dp[to[edge]], dp[res[i]] + 1);
}

int main()
{
    memset(points, -1, sizeof(points));
    memset(to, -1, sizeof(to));
    memset(indeg, 0, sizeof(indeg));
    cin >> n >> m;
    int a, b;
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b, add_edge(a, b);
        indeg[b] += 1;
    }
    toposort();
    DP();
    for (int i = 1; i <= n; i++)
        cout << dp[i] << endl;
    return 0;
}

P1122:最大子树和题解

思路

设一个F[n+1]为树形DP的数组。在点i上，对于每一个子节点j，都有F[j] = dis[i] + max(0, F[j])。其中dis是美丽指数。

代码

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

using namespace std;
// the tree;
const int maxn = 160010;
int n;
int dis[maxn];
int to[maxn];
int next[maxn];
int point[maxn];
int current = 0;
int F[maxn];
int ans = 0;

void add_edge(int src, int dst)
{
    next[current] = point[src];
    to[current] = dst;
    point[src] = current;
    current++;
}
// core code: search subtrees and add them up to F[curt],
// in the meanwhile, get the ans;
void DFS(int curt, int fat)
{
    F[curt] = dis[curt];
    for (int i = point[curt]; i != -1; i = next[i])
    {
        int dst = to[i];
        if (dst == fat)
            continue;
        DFS(dst, curt);
        F[curt] += max(0, F[dst]);
    }
    ans = max(ans, F[curt]);
}
// initialize;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> dis[i];
    fill(point, point + n + 1, -1);
    fill(next, next + n + 1, -1);
    fill(F, F + n + 1, 0);
    int a, b;
    for (int i = 0; i < n - 1; i++)
    {
        cin >> a >> b;
        add_edge(a, b), add_edge(b, a);
    }
    DFS(1, 0);
    cout << ans;
    return 0;
}

P2678:跳石头题解 & 二分答案原理

暑假和小学神仙们集训的时候发过这道题，一直不知道如何去解决。一个月前crazydave大佬给我简述过二分答案的原理，而蒟蒻我今天才搞定这些。

我们先来看例题：洛谷P2678

这是一道NOIP提高组的简单题（我太菜了），主要是通过枚举答案，在每次枚举时检测能不能符合要求即可。先看代码：

// P2678.cpp
#include <iostream>

using namespace std;

const int maxn = 500020;
int L, N, M;
int D[maxn];

bool check(int num)
{
    int last = 0;
    int cnt = 0;
    for (int i = 0; i <= N; i++)
        if (D[i] - last < num)
            cnt++;
        else
            last = D[i];
    if (cnt > M)
        return false;
    return true;
}

void solve()
{
    int left = 0;
    int right = L;
    int ans = 0;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (check(mid))
            left = mid + 1, ans = mid;
        else
            right = mid - 1;
    }
    cout << ans;
}

int main()
{
    cin >> L >> N >> M;
    for (int i = 0; i < N; i++)
        cin >> D[i];
    D[N] = L;
    solve();
    return 0;
}

check函数就是验证答案num（也就是我们枚举出来的答案）是否符合要求，在这里便是检测当最小距离为num时，移走的石子会不会超过限制。如果超过了，返回false，二分便会把区间调为[left,mid-1]，以降低最大值来试探限制；没有超过，则返回true，二分把区间调整为[mid+1,right]，以追求更大的最大值。

抽象化分析结果

准备枚举一道题答案之前，请考虑二分答案。如果可以二分答案，那么时间复杂度会极度降低，从O(n^2)转变为O(n log n)。二分答案的结构就是二分代码和检验答案正确性代码。如果能通过正确性检查，那么追求更大（小）的答案并重新枚举；如果无法通过，则把区间调整，在较小（大）区间内追求更大（小）的答案。亦复如此。