E

Before the Beginning

转载请将本段放在文章开头显眼处，如有二次创作请标明。
原文链接：https://www.codein.icu/nowcoderweekly16/

似乎网上没这道题题解，于是全场……
一开始看错题了，以为黑白球必须分别扎堆，其实不需要。
可以使用动态规划来解决，由于要求顺序，那么：
设前 个球中，有 个白球， 个黑球，那么对应的黑白球编号一定是 和 。
此时决定第 个球，选择白球或者黑球进行转移，即满足了最优子结构。
设 为前 个球， 个白球， 个黑球的状态。
如果决定第 个球为白球，，其中 为编号为 的球移到 的代价。
黑球同理。
考虑如何计算这个代价，显然可以记录 代表编号为 的球的坐标，代价即 。
然而在前面的过程中，即移动前 个球时， 可能发生了变化。
如果移动的球在 前，则对其无影响，如果在其后，则 。
统计当前状态，编号 的白球与 的黑球中，有多少个在 中，即可知道该球的 向后了多少。
计算出相应代价进行DP即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <ctype.h>
const int maxn = 4e3 + 100;
int n;
int wnum,bnum;
char s[10];
int f[maxn][maxn];//前i个，白色前j个
int id[maxn],col[maxn];
int wpos[maxn],bpos[maxn];
int wcnt[maxn][maxn],bcnt[maxn][maxn];
inline int getw(int l,int r,int x){return wcnt[r][x] - wcnt[l - 1][x];}
inline int getb(int l,int r,int x){return bcnt[r][x] - bcnt[l - 1][x];}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n * 2; ++i)
    {
        scanf("%s", s + 1), scanf("%d", id + i);
        col[i] = (s[1] == 'B');
        if(col[i]) bpos[id[i]] = i;
        else wpos[id[i]] = i;
    }
    for(int i = 1;i<=2*n;++i) 
    {
        if (col[i] == 0) for (int j = id[i]; j <= n; ++j) wcnt[i][j]++;
        else for (int j = id[i]; j <= n; ++j) bcnt[i][j]++;
        for (int j = 1; j <= n; ++j) wcnt[i][j] += wcnt[i - 1][j], bcnt[i][j] += bcnt[i - 1][j];
    }
    memset(f, 0x3f, sizeof(f));
    f[0][0] = 0;
    for (int i = 1; i <= 2 * n; ++i)
    {
        for (int j = 0; j <= n && j <= i; ++j)
        {
            int bl = i - j;
            if (j <= i - 1)
            {
                //choose black to fill i
                int bp = bpos[bl];
                f[i][j] = f[i - 1][j] + bp - i + getw(bp + 1, 2 * n, j) + getb(bp + 1, 2 * n, bl - 1);
            }
            if (j)
            {
                //choose white to fill i
                int wp = wpos[j];
                f[i][j] = std::min(f[i][j], f[i - 1][j - 1] + wp - i + getw(wp + 1, 2 * n, j - 1) + getb(wp + 1, 2 * n, bl));
            }
        }
    }
    printf("%d\n",f[2*n][n]);
    return 0;
}