首页 > 代码库 > bzoj 4664: Count
bzoj 4664: Count
这道题和bzoj上一道叫魔法碰撞的题很像，只不过做法更加巧妙了。
一开始的想法是$f[i][j][k][0/1/2]$表示后i个数有j段当前混乱程度为k的方案，最后一维表示边界还能放几个。
转移的时候枚举每个数是山峰山谷或者中间的数，然后让混乱程度加上$h$或减去$h$.
但是这样做第三维的状态数太大了。
转变思路，从小到大枚举i，让第三维的意义变为当前每一段中的数两两之间的混乱度加上之后合并完所有段后至少会产生的混乱度。
每次$k=k+(j*2+l-2)*(h[i+1]-h[i])$,就是现在每个空的代价会加上$(h[i+1]-h[i])$,现在放$h[i+1]$的时候不会产生新的代价。
这样第三维就是递增的了，最大就是L。
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#define N 105using namespace std;const int p = 1000000007;int n,L;int h[N];int f[2][105][1205][3];int main(){// freopen("count.in","r",stdin);// freopen("count.out","w",stdout); scanf("%d%d",&n,&L); for(int i=1;i<=n;i++)scanf("%d",&h[i]); sort(h+1,h+n+1); if(h[n]-h[1]>L) { puts("0");return 0; } if(n==1) { puts("1"); return 0; } // f[i][j][k][0] 前i个数被分成了j段混乱度是k int now=0,pre=1; f[0][1][0][1]=2; f[0][1][0][2]=1; for(int i=1;i<n;i++) { now^=1;pre^=1; memset(f[now],0,sizeof(f[now])); // 处理i+1 for(int j=1;j<=i;j++) { for(int k=0;k<=L;k++) { for(int l=0;l<=2;l++) { if(f[pre][j][k][l]) { int tmp=f[pre][j][k][l]; int tp=k+(h[i+1]-h[i])*(2*j+l-2); if(tp>L)continue; if(l) { (f[now][j][tp][l-1]+=1LL*tmp*l%p)%=p; (f[now][j+1][tp][l-1]+=1LL*tmp*l%p)%=p; } (f[now][j-1][tp][l]+=1LL*tmp*(j-1)%p)%=p; (f[now][j+1][tp][l]+=1LL*tmp*(j-1+l)%p)%=p; (f[now][j][tp][l]+=1LL*tmp*(2*j-2+l)%p)%=p; } } } } } int ans=0; for(int i=0;i<=L;i++) { ans+=f[now][1][i][0]; ans%=p; } printf("%d\n",ans); return 0;}
bzoj 4664: Count
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。