[ARC213A] Swapping Game

· · 题解

被诈骗了半小时，呜呜。

思路：

首先，一个 A 通过相邻交换变成 B 的最小次数是显然的：

设 w(i, j) 表示 P_i \to P_j 的最小次数，那么显然有 dp：

dp_i = \max\limits_{w(j, i) \le i - j} (dp_j + c_i)

直接暴力做至少是 O(n^2) 的，无法通过；注意到 w(i, j) \le \frac{L(L - 1)}{2} 即 O(L^2) 级别的；于是对于 i - j > \frac{L(L - 1)}{2} 的 j，一定满足条件。

所以只需要枚举 i 前面 \le \frac{L(L - 1)}{2} 个 j 判定是否满足限制即可；暴力求逆序对，时间复杂度为 O(NL^3)。

完整代码：

 #include<bits/stdc++.h>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define add(x, y) ((x + y >= mod) ? (x + y - mod) : (x + y))
#define dec(x, y) ((x - y < 0) ? (x - y + mod) : (x - y))
#define popcnt(x) __builtin_popcount(x)
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
const int N = 3e4 + 10, M = 10, MM = 40;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
      write(x / 10);
    putchar(x % 10 + '0');
}
int n, l, ans;
int c[N], h[N], t[N], s[N], p[N][M];
int mx[N], dp[N];
bool vis[N][MM];
int main(){
    n = read(), l = read();
    for(int i = 1; i <= l; ++i)
      p[0][i] = i;
    for(int i = 1; i <= n; ++i){
        c[i] = read();
        for(int j = 1; j <= l; ++j)
          p[i][j] = read();
    }
    int lim = (l * (l - 1) >> 1);
    for(int i = 1; i <= n; ++i){
        for(int k = 1; k <= l; ++k)
          t[p[i][k]] = k;
        for(int j = i - 1; i - j <= lim && j >= 0; --j){
            for(int k = 1; k <= l; ++k)
              h[k] = t[p[j][k]];
            int sum = 0;
            for(int x = 1; x <= l; ++x)
              for(int y = x + 1; y <= l; ++y)
                sum += h[x] > h[y];
            vis[i][i - j] = (sum <= i - j);
        }
    }
    for(int i = 1; i <= n; ++i){
        dp[i] = -1e9;
        for(int j = i - 1; i - j <= lim && j >= 0; --j)
          if(vis[i][i - j])
            dp[i] = max(dp[i], dp[j] + c[i]);
        if(i - lim - 1 >= 0)
          dp[i] = max(dp[i], s[i - lim - 1] + c[i]);
        ans = max(ans, dp[i]);
        s[i] = max(s[i - 1], dp[i]);
    }
    write(ans);

    return 0;
}