电影网站空间配置,网站开发毕业设计文档,商丘seo公司,wordpress文章发布正题
题目链接:https://www.luogu.com.cn/problem/P7519 题目大意 nnn个队伍#xff0c;队伍之间按照得分从小到大排名#xff0c;得分相同的按照编号从小到大排。开始时每个队伍有个初始得分aia_iai#xff0c;和一个额外分bib_ibi#xff0c;主持人会按照bib_ibi不…正题
题目链接:https://www.luogu.com.cn/problem/P7519 题目大意
nnn个队伍队伍之间按照得分从小到大排名得分相同的按照编号从小到大排。开始时每个队伍有个初始得分aia_iai和一个额外分bib_ibi主持人会按照bib_ibi不降的顺序让每个队伍的得分加上bib_ibi并且要求每次加上后这个队伍都变成第一名。
已知每个队伍的初始分aaa和额外分的和mmm求有多少种公布额外分的序列。
1≤n≤13,1≤m≤500,0≤ai≤1041\leq n\leq 13,1\leq m\leq 500,0\leq a_i\leq 10^41≤n≤13,1≤m≤500,0≤ai≤104 解题思路
显然地一点是我们考虑一个序列合法时bib_ibi的和的最小值然后和mmm进行比较
开始思路时卡了假设已经排好了一部分我们需要把一个新的排在后面此时会有两个限制
这个队伍的得分aibia_ib_iaibi必须是已经公布的里面最大的或相同的序号最小的bib_ibi必须是已经公布的里面最大的。
显然记录上这两个限制进行的dpdpdp并不方便考虑如何去掉一个限制因为bib_ibi是我们可以任意调整的并且要求递增可以每次操作都让后面所有数字的bib_ibi都同时加值这样就不需要考虑第二个限制了。
然后是第一个限制如何处理注意到我们在刚刚的情况下假设限制最后公布的一个是iii而下一个公布的是jjj那么此时有bjbib_jb_ibjbi所以此时两个数加上bbb之后的差值不变所以直接拿ai−aja_i-a_jai−aj就可以知道后面的bjb_jbj要加上多少了。
那么做法已经显然了设fs,i,jf_{s,i,j}fs,i,j表示现在已经插入的数状态为sssbib_ibi的和为iii目前最后一个公布的是jjj然后O(n)O(n)O(n)转移即可。
时间复杂度O(2nmn2)O(2^nmn^2)O(2nmn2)实际上很多状态是不会到达的所以能过。 code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N13;
ll n,m,ans,a[N],c[1N],f[1N][501][N];
signed main()
{scanf(%lld%lld,n,m);ll pos0;for(ll i0;in;i){scanf(%lld,a[i]);if(a[i]a[pos])posi;}f[0][0][pos]1;ll MS(1n);for(ll s1;sMS;s)c[s]c[s-(s-s)]1;for(ll s0;sMS;s)for(ll k0;km;k)for(ll i0;in;i){if(!f[s][k][i])continue;for(ll j0;jn;j){if((sj)1)continue;ll wmax(a[i]-a[j](ji),0ll)*(n-c[s]);if(kwm)continue;f[s^(1j)][kw][j]f[s][k][i];}}for(ll i0;im;i)for(ll j0;jn;j)ansf[MS-1][i][j];printf(%lld\n,ans);return 0;
}
