Kalorona

P1841:「JSOI2007」重要的城市题解

思路

这道题是lornd巨佬给我写的。由于我太菜了，只能放弃看题解。看完题解之后，发现解法甚是巧妙，便来分享一则。

原理就是在无向图floyed求最短路的时候，每发现一次新的路径就要更新一次重要点。策略如下：

  1. 如果原路径比现在的路径要长，那么更新路径，并且在cities[i][j]中记录点k。
  2. 如果原路径和现在的路径相等，那么重要点不唯一，那么把cities[i][j]记录为-1。

最终在cities里面搜索不为-1的元素，排序输出即可。

代码

// P1841.cpp
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
#define ll long long
ll mat[300][300];
int dp[300][300];
bool ans[500];
const ll INF = (ll)(0x7fffffff) / 3;
int n, m;

void floyed()
{
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            if (i != k)
                for (int j = 1; j <= n; j++)
                    if (i != j && j != k)
                        if (mat[i][k] + mat[k][j] < mat[i][j])
                            mat[i][j] = mat[i][k] + mat[k][j], dp[i][j] = k;
                        else if (mat[i][k] + mat[k][j] == mat[i][j])
                            dp[i][j] = -1;
}

void addpath(int src, int dst, ll w)
{
    mat[src][dst] = mat[dst][src] = w;
}

int main()
{
    fill(mat[0], mat[0] + 300 * 300, INF);
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        ll a, b, c;
        cin >> a >> b >> c;
        addpath(a, b, c);
    }
    floyed();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (dp[i][j] != -1)
                ans[dp[i][j]] = true;
    bool flag = true;
    for (int i = 1; i <= n; i++)
        if (ans[i])
            cout << i << " ", flag = false;
    if (flag)
        cout << "No important cities.";
    return 0;
}

P1052:过河题解

思路

本题数据很大，如果用传统的路径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;
}

P1156:垃圾陷阱

思路

这题我写了一天才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;
}

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