首页 > 代码库 > BZOJ4742 : [Usaco2016 Dec]Team Building
BZOJ4742 : [Usaco2016 Dec]Team Building
如果我们将两个人拥有的牛混在一起，并按照战斗力从小到大排序，同时把第一个人选的牛看成$)$，第二个人选的牛看成$($的话，那么我们会发现一个合法的方案对应了一个长度为$2k$的括号序列。
于是DP即可，$f[i][j][k]$表示考虑了前$i$头牛，目前选了$j$个左括号，括号序列的前缀和为$k$的方案数。
时间复杂度$O(nk^2)$。
#include<cstdio>#include<algorithm>const int N=2010,M=13,P=1000000009;int n,m,K,cnt,i,j,k,f[N][M][M];struct E{int x,y;E(){}E(int _x,int _y){x=_x,y=_y;}}a[N];inline bool cmp(const E&a,const E&b){return a.x==b.x?a.y<b.y:a.x>b.x;}inline void up(int&x,int y){x+=y;if(x>=P)x-=P;}int main(){ scanf("%d%d%d",&n,&m,&K); while(n--)scanf("%d",&k),a[++cnt]=E(k,1); while(m--)scanf("%d",&k),a[++cnt]=E(k,-1); std::sort(a+1,a+cnt+1,cmp); for(f[0][0][0]=i=1;i<=cnt;i++)for(j=0;j<=K;j++)for(k=0;k<=K;k++)if(f[i-1][j][k]){ up(f[i][j][k],f[i-1][j][k]); if(a[i].y>0)up(f[i][j+1][k+1],f[i-1][j][k]); else if(k)up(f[i][j][k-1],f[i-1][j][k]); } return printf("%d",f[cnt][K][0]),0;}
BZOJ4742 : [Usaco2016 Dec]Team Building
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。