正题

题目链接:https://www.luogu.com.cn/problem/P7519

---

题目大意

$n$个队伍，队伍之间按照得分从小到大排名，得分相同的按照编号从小到大排。开始时每个队伍有个初始得分$a_i$，和一个额外分$b_i$，主持人会按照$b_i$不降的顺序让每个队伍的得分加上$b_i$，并且要求每次加上后这个队伍都变成第一名。

已知每个队伍的初始分$a$和额外分的和$m$，求有多少种公布额外分的序列。

$1\le n\le 13,1\le m\le 500,0\le a_i\le 10^4$

---

解题思路

显然地一点是我们考虑一个序列合法时$b_i$的和的最小值，然后和$m$进行比较

开始思路时卡了，假设已经排好了一部分，我们需要把一个新的排在后面，此时会有两个限制：

这个队伍的得分$a_i+b_i$必须是已经公布的里面最大的（或相同的序号最小的）

$b_i$必须是已经公布的里面最大的。

显然记录上这两个限制进行的$dp$并不方便，考虑如何去掉一个限制，因为$b_i$是我们可以任意调整的，并且要求递增，可以每次操作都让后面所有数字的$b_i$都同时加值，这样就不需要考虑第二个限制了。

然后是第一个限制如何处理，注意到我们在刚刚的情况下，假设限制最后公布的一个是$i$，而下一个公布的是$j$，那么此时有$b_j=b_i$，所以此时两个数加上$b$之后的差值不变，所以直接拿$a_i-a_j$就可以知道后面的$b_j$要加上多少了。

那么做法已经显然了，设$f_{s,i,j}$表示现在已经插入的数状态为$s$，$b_i$的和为$i$，目前最后一个公布的是$j$，然后$O(n)$转移即可。

时间复杂度：$O(2^{n}m{n}^2)$，实际上很多状态是不会到达的，所以能过。

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=13; ll n,m,ans,a[N],c[1<<N],f[1<<N][501][N]; signed main() {scanf("%lld%lld",&n,&m);ll pos=0;for(ll i=0;i<n;i++){scanf("%lld",&a[i]);if(a[i]>a[pos])pos=i;}f[0][0][pos]=1;ll MS=(1<<n);for(ll s=1;s<MS;s++)c[s]=c[s-(s&-s)]+1;for(ll s=0;s<MS;s++)for(ll k=0;k<=m;k++)for(ll i=0;i<n;i++){if(!f[s][k][i])continue;for(ll j=0;j<n;j++){if((s>>j)&1)continue;ll w=max(a[i]-a[j]+(j>i),0ll)*(n-c[s]);if(k+w>m)continue;f[s^(1<<j)][k+w][j]+=f[s][k][i];}}for(ll i=0;i<=m;i++)for(ll j=0;j<n;j++)ans+=f[MS-1][i][j];printf("%lld\n",ans);return 0; }

总结

以上是生活随笔为你收集整理的P7519-[省选联考 2021 A/B 卷]滚榜【状压dp】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。