题解：AT_arc177_f [ARC177F] Two Airlines

· · 题解

感觉很牛的题啊！sto wzy orz 直接自己切了。

题意：现在从 0\to n 一共有 n 条道路，每条道路有颜色黑白，有两种颜色的人，给出他们的位置，每一个人有黑或白的颜色，一个人通过对应颜色的道路时不消耗代价，否则消耗 1 的代价，现在有一个硬币在 0，每一个人在硬币的位置的时候就可以把硬币拿过来携带在自己身上，问把硬币带到 n 的最小代价。

做法：

注意到，我对于黑色的人和白色的人肯定是一直保持相对顺序的，并且路径一定形如，我一个人回来接这个硬币，然后往后走一段，若干段这样，所以可以很容易地设计出来一个 dp：dp_{i,j,k,0/1} 代表我现在黑色人用了前 i 个，白色人用了前 j 个，硬币在 k，目前携带的人颜色为黑/白，转移显然。

然后想想这个东西很没有前途，因为这三维都一定是要记录的。我们考虑换一换定义，我们现在记录的是绝对的位置，比如我黑色的人总共 x 个我用了前 i 个，那我们考虑变成相对的，也就是，在我这个位置之后有 j 个位置用过了，白色那一维类似，转移也是可以容易做的。感觉如果像我一样绕死在绝对的那个 dp 就基本没啥前途。

但是这样仍然没有优化我们的复杂度，还是三次的，这个时候我们就得想办法优化一下我们的 dp，考虑一些贪心，比如路径比较远的时候我们就不让别人帮这种，虽然都不太对，但是贪着贪着你会有点感觉，就是，如果两个黑色人都越过了 i，说明应该中间有一段非常长的白色，这段的代价太大了以至于我们要先切换一次白色，再切换一次黑色这样带过来，否则我们直接让黑色冲过去就可以了。画个图：

这里用红蓝代替黑白。

考虑让黑色冲过去会改变哪些代价，会多一个 x，少一个白色，但是我们先不管，就当是 0，不影响我们分析。然后会节省 y 这一段，因为第二段黑色过来要走那一段 y，那么要求 x>y，然后你再把 y 展开成多段，发现会有比如 y>z，然后就会要求 x>2z，你会发现这样的限制是一直在翻倍的！所以我们第 2,3 维完全没有必要开 O(n)，开成 \log 就可以了。

这样这个题就做完了，复杂度两只 \log。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 6e4 + 5, lim = 20;
int n, m, t[maxn][2], a[maxn], s[maxn][2];
int dp[maxn][lim + 5][lim + 5][2], nxt[maxn][lim + 5][2];
vector<int> vec[2];
signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        char c; cin >> c;
        a[i] = (c == 'A' ? 1 : 0); 
    }
    for (int i = 1; i <= n; i++)
        s[i][0] = (s[i - 1][0] + (a[i] == 1)),
        s[i][1] = (s[i - 1][1] + (a[i] == 0));
    for (int i = 1; i <= m; i++) {
        int p; char c; cin >> p >> c;
        vec[(c == 'A' ? 1 : 0)].push_back(p);
        t[p][(c == 'A' ? 1 : 0)]++;
    }
    sort(vec[0].begin(), vec[0].end()), sort(vec[1].begin(), vec[1].end());
    for (int i = 0; i <= n; i++) {
        int s1 = lower_bound(vec[0].begin(), vec[0].end(), i) - vec[0].begin();
        int s2 = lower_bound(vec[1].begin(), vec[1].end(), i) - vec[1].begin();
        for (int j = 1; j <= lim; j++) {        
            nxt[i][j][0] = (s1 < vec[0].size() ? vec[0][s1] : -1);
            nxt[i][j][1] = (s2 < vec[1].size() ? vec[1][s2] : -1);
            s1++, s2++;
        }
    }
    memset(dp, 0x3f, sizeof(dp));
    if(nxt[0][1][0] != -1)
        dp[0][1][0][0] = s[nxt[0][1][0]][0];
    if(nxt[0][1][1] != -1)
        dp[0][0][1][1] = s[nxt[0][1][1]][1];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= lim; j++)
            for (int k = 0; k <= lim; k++) {
                for (int l = 0; l <= 1; l++) {
                    if(j < lim && nxt[i][j + 1][0] != -1)
                        dp[i][j + 1][k][0] = min(dp[i][j + 1][k][0], dp[i][j][k][l] + s[nxt[i][j + 1][0]][0] - s[i][0]);
                    if(k < lim && nxt[i][k + 1][1] != -1)
                        dp[i][j][k + 1][1] = min(dp[i][j][k + 1][1], dp[i][j][k][l] + s[nxt[i][k + 1][1]][1] - s[i][1]);
                }
            }
        for (int j = 0; j <= lim; j++)
            for (int k = 0; k <= lim; k++)
                for (int l = 0; l <= 1; l++)
                    dp[i + 1][max(0ll, j - t[i][0])][max(0ll, k - t[i][1])][l] = min(dp[i + 1][max(0ll, j - t[i][0])][max(0ll, k - t[i][1])][l], dp[i][j][k][l] + (l != a[i + 1]));
    }
    int ans = 9e18;
    for (int i = 0; i <= lim; i++)
        for (int j = 0; j <= lim; j++)
            for (int l = 0; l <= 1; l++)
                ans = min(ans, dp[n][i][j][l]);
    cout << ans << endl;
    return 0;
}