一、题目
二、解法
考试时把题目看错了，没有注意到 (a_i) 不降的条件。
考虑要求的东西是可能的排名情况，也就是求合法排列个数，状压可以将 (O(n!)) 的排列枚举优化成 (O(2^n))，那么这道题肯定会用上它。
如果我们不考虑 (a_i) 不降的限制，发现这个题根本做不出来。因为你不知道某集合的最大值是谁，就算你记录了是谁也不知道是多少。那么考虑把 (a_i) 不降当成条件而非限制。
某东西不降可以自然的联想到差分技巧，也就是当前我们把某个人 (i) 的过题数增加 (x)，那么不在状压集合里的人的过题数也增加 (x)，下次考虑到某个人 (j) 的时候 (i,j) 的相对过题差值就没有变化，可以当成初始过题数来考虑，所以我们只需要记录最大值是哪个人即可。
设 (dp[s][i][k]) 为考虑集合 (s) 中的人，最后公布排名的人是 (i)，已经分配的过题数是 (k) 的顺序情况数，转移考虑刷表法，枚举下一个公布排名的人 (j)，设 (w(j,i)) 表示初始情况下 (j) 超过 (i) 的最小过题数乘以剩下的总人数，转移：
[dp[s|2^j][j][k+w(j,i)]leftarrow dp[s][i][k]
]
话说 ( t CCF) 给的时间复杂度越来越离谱了，(O(2^nn^2m)) 看上去就跑不动啊 (...)
三、总结
做题时我们会忽略某限制来做，再考虑加上某限制。但如果忽略某限制做不起就一定要注意了，可以把限制当成条件！
差分技巧的使用十分关键，(dp) 的时候差分放状态里可以叫消耗提前计算。
#include <cstdio>
#include <iostream>
using namespace std;
#define pii pair<int,int>
#define make make_pair
#define ll long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m;pii mx,a[15];ll ans,dp[1<<13][15][505];
int w(pii a,pii b)
{
int t=b.first-a.first;
return max(0,t+(b.second<a.second));
}
signed main()
{
n=read();m=read();
for(int i=0;i<n;i++)
{
a[i]=make(read(),i);
if(mx.first<a[i].first) mx=a[i];
if(mx.first==a[i].first && mx>a[i]) mx=a[i];
}
for(int i=0;i<n;i++)
{
int t=n*w(a[i],mx);
if(t<=m) dp[1<<i][i][t]=1;
}
for(int s=0;s<(1<<n);s++)
{
int t=__builtin_popcount(s);
for(int i=0;i<n;i++)
{
if((s&(1<<i))==0) continue;
for(int l=0;l<=m;l++)
{
if(dp[s][i][l]==0) continue;
for(int j=0;j<n;j++)
{
if(s&(1<<j)) continue;
int r=(n-t)*w(a[j],a[i]);
if(l+r<=m)
dp[s|(1<<j)][j][l+r]+=dp[s][i][l];
}
}
}
}
for(int i=0;i<n;i++)
for(int j=0;j<=m;j++)
ans+=dp[(1<<n)-1][i][j];
printf("%lld
",ans);
}