题解 [省选联考 2021 A:B 卷] 滚榜

题目大意：

给定 \(n,m\) 和长度为 \(n\) 的数组 \(a_i\) 。问有多少种排列 \(p_n\) ，使得存在数组 \(b_i\) ，满足

  • \(b_i\) 单调不减
  • \(\sum_{i=1}^n b_i=m\)
  • 依次对 \(a_{p_i}\) 加上 \(b_i\) ，满足操作后 \(a_{p_i}\) 为最大元素。

数据范围：\(1\le n\le 13,1\le m\le 500,0\le a_i\le 10^4\) .

知识储备：状态压缩，差分

题目难度：省选/USACO Platinum

解析：

（从数据范围不难想到这是状压dp，那么如何设计状态和优化dp就是解题的关键。）

首先想到这样的 dp ， \(f_{S,i,j}\) 为前面选取的状态为 \(S\) ，上一个数为 \(i\) ，当前的 \(\sum b_i\) 为 \(j\) 。然而为了保证 \(b_i\) 的单调性，我们还要加一维 \(k\) 用来记录上一个 \(b_i\) 的值。注意到我们要求排列的方案数，于是可以贪心取 \(b_i\) 来尽量满足性质。暴力转移即可，时间复杂度为 \(O(2^nn^2m^2)\) 。

然后你会发现这个 dp 甚至不如贪心暴力跑全排列，后者能得到 60 pts 的好成绩

考虑优化 dp 状态，而 \(S,i,j\) 对于我们考虑转移是必须的，所以想去掉 \(k\) 这一维。\(b_i\) 单调不减的性质提示了差分，运用的思想和下面这道题类似。

CF626F Group Projects

于是设 \(d_i=b_i-b_{i-1}\ge 0\) ，有 \(d_i=\max(a_{p_{i-1}}-a_{p_i},0)\) ，并且 转化后，代码实现就相对简单了。

时间复杂度：\(O(2^nn^2m)\) .

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=14,M=505;
int n,m,a[N],c[N][N],ppc[1<<N],id[1<<N],mx;
ll ans,f[1<<N][N][M];
int main(){
    n=read(),m=read();
    rep(i,1,n){
        a[i]=read();
        if(a[i]>a[mx])mx=i;
        id[1<<(i-1)]=i;
    }
    rep(i,1,n)rep(j,1,n){
        c[i][j]=max(0,a[i]-a[j]+(i<j));//注意编号小的队伍排名靠前
    }
    rep(i,1,n){
        int sum=n*(a[mx]-a[i]+(mx<i));
        if(sum<=m)f[1<<(i-1)][i][sum]=1;
    }
    int up=(1<<n)-1;
    rep(i,1,up)ppc[i]=ppc[i>>1]+(i&1);
    rep(S,1,up){
        for(int t=S;t;t-=t&-t){
            int pos=id[t&-t];
            rep(sum,0,m)rep(i,1,n){
                if((S>>(i-1))&1)continue;
                int k=sum+(n-ppc[S])*c[pos][i];
                if(k<=m)f[S|1<<(i-1)][i][k]+=f[S][pos][sum];
            }
        }
    }
    rep(i,1,n)rep(j,0,m)ans+=f[up][i][j];
    printf("%lld\n",ans);
    return 0;
}

Comments