Educational Codeforces Round 151 (Rated for Div. 2)E. Boxes and Balls（数学，动态规划）

ACMER-XiCen / 2023-08-28 / 原文

题目链接：https://codeforces.com/contest/1845/problem/E

题意：

给定长度为n且只含0和1的数组，你可以进行以下操作：

交换相邻的0和1；

给正整数k，问经过k次操作后，会有多少种本质不同的结果；

分析：

如果1比0多，我们可以把他们取反（让0比1多，结果是一样的）

设计状态dp[i][j][k]表示用k步使得前i个里面有j个1；

可以发现，上诉的操作后，1的相对位置是不会发生变化的；

那么我们可以让第j个1去到i位置上；

设第j个1的位置是p[j]，那么，转移方程是：

dp[ i ][ j ][ k ] = dp[ i - 1 ][ j ][ k ] + dp[ i - 1 ][ j - 1 ][ k - abs ( p[ j ] - i ) ];

但时间复杂度为O（n^2*k），考虑优化：

可以发现，要将前x个1挪出前i格，那么至少需要x^2步，反之同理；

前i格在操作过后1的个数与原来相差的值最大为 k ^ (1/2) ;

那么在这个范围内转移即可，时间复杂度为O（n*k^(3/2));

代码：

#include<bits/stdc++.h>

#define int long long

const int N = 1500 + 15;
const int mod = 1e9 + 7;

int dp[N][N];

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    int n, m;
    std::cin >> n >> m;
    std::vector<int> a(n + 1, 0);
    int sum = 0;
    for (int i = 1; i <= n; ++i)std::cin >> a[i], sum += a[i];
    if (sum << 1 > n)for (int i = 1; i <= n; ++i)a[i] ^= 1;
    sum = 0;
    std::vector<int> p, s(n + 1, 0);
    p.push_back(0);
    for (int i = 1; i <= n; ++i) {
        s[i] = s[i - 1] + a[i];
        sum += a[i];
        if (a[i])p.push_back(i);
    }

    int b = sqrt(sum) * 3;//猜猜为什么是3，不是2：）
    dp[0][0] = 1;

    for (int i = 1; i <= n; ++i)
        for (int j = std::min({i, s[i] + b, sum}); j >= s[i] - b && j; --j) {
            int c = abs(p[j] - i);
            for (int k = c; k <= m; ++k)dp[j][k] = (dp[j][k] + dp[j - 1][k - c]) % mod;
        }

    int ans = 0;
    for (int i = m; i >= 0; i -= 2)ans = (ans + dp[sum][i]) % mod;

    std::cout << ans << "\n";

    return 0;
}