[省选联考 2021]滚榜-白红宇

[省选联考 2021]滚榜

阅读量：245 次

发布时间：2019-03-01

本文共 1997 字，大约阅读时间需要 6 分钟。

题解

~~$n!$ 的暴力竟然有60pts！！！~~

首先， $n\leqslant 13$ 这个范围是很小的，我们很容易想到状压dp。

由于它要求的是方案数，而选择的

b_{i}

又要求是递增的，我们需要将选择状态，上一个点，总的已选择题数都加入状态，所以我们得到的是一个

dp_{S,i,j,k}

的4维dp，最后答案就是

dp_{2^n-1,n,0-m,m}

。

再加上需要转移的点于当前选择题数，我们成功将时间复杂度搞到了

O\left(2^nn^2m^3\right)

~~，这还不如暴力了吧~~。

由于题目要求的是排名顺序种类数，我们没必要让当前点将所有能取的取值都取一遍，只要总的题目数是不超过 $m$ 的，我们就一定有一种方法可以让当前排名顺序合法。

所以，我们从

i

转移到

j

时，只需要加上

j

所需的最小取值，时间复杂度变成了

O\left(2^nn^2m^2\right)

~~，好像还是不如暴力~~。

我们发现，由于 $b_{i}$ 是不降的，所以当前面的加上 $b_{i}$ 后，后面的也相当于同时加上了 $b_{i}$ ，此时它们之间的差值是不变的，我们可以用 $\Delta=b_{j}-b_{i}$ 来表示状态。

我们在转移时先将

b_{i}

对于每个还未加的数都先加上，将总数加上

n-bit_{S})b_{i}

后

\Delta

的限制就与单个点的选值无关了，至于总值有关。

这样，我们就可以将原来的四维dp变成

dp_{S,i,j}

的三维，时间复杂度也降成了

O\left(2^nn^2m\right)

，可以过了。~~虽然看起来有一点卡常，但这题数据好没有梯度呀~~

源码

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             using namespace std;#define lowbit(x) (x&-x)#define reg register#define mkpr make_pair#define fir first#define sec secondtypedef long long LL;typedef unsigned long long uLL;typedef unsigned int uint;typedef pair
             
               pii;const int INF=0x7f7f7f7f;const double PI=acos(-1.0);template
              
               _T Fabs(_T x){ return x<0?-x:x;}template
               
                void read(_T &x){ _T f=1;x=0;char s=getchar(); while(s>'9'||s<'0'){ if(s=='-')f=-1;s=getchar();} while('0'<=s&&s<='9'){ x=(x<<3)+(x<<1)+(s^48);s=getchar();} x*=f;}int n,m,bit[(1<<13)+5],a[15],dif[15][15],k,maxx,lim;LL dp[(1<<13)+5][15][505],ans;signed main(){ read(n);read(m);for(reg int i=1;i<=n;++i)read(a[i]);lim=(1<
                
                 >1]+(i&1); for(reg int i=1;i<=n;++i)if(a[i]>maxx)maxx=a[i],k=i; for(reg int i=1;i<=n;++i)for(int j=1;j<=n;++j)dif[i][j]=max(0,a[j]-a[i]+(i>j)); for(reg int i=1;i<=n;++i)if(dif[i][k]*n<=m)dp[1<
                 
                  m)continue; dp[i|(1<

谢谢！！！

转载地址：http://lrqt.baihongyu.com/

你可能感兴趣的文章