TopCoder SRM 666 Div1
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
----------------------------------------------------------
这场号666啊
----------------------------------------------------------
Easy:
没写
感觉是个SB树形DP
----------------------------------------------------------
Medium:
题意是说,把n个盒子按顺序放到n个位置上(每个位置只能放一个箱子),每一步的价值是(n-x),其中x=这个位置左右两边的位置上箱子的个数,一个放法的价值是每一步的价值之积,问所有放法的价值和,n<=4000
设f[i][j][k]表示有n个箱子要放,序列的最左边的左边有没有箱子,序列的最右边的右边有没有箱子
考虑枚举第一个箱子的位置,然后就把序列分成了左右两段,乘以一个组合数就可以转移了
比如f[n][0][0] = ∑(i=1,n)n*C(n-1,i-1)*f[i-1][0][1]*f[n-i][1][0]
然后f[n][0][0就是答案
----------------------------------------------------------
Hard:
说你有一个长度为n的01串,有m个限制,每个限制是[l,r]这个区间内必须有偶数个1,保证这些区间不相交(可以包含),然后不能有连续的超过k个1,n<=10^9,m<=50,k<=5
说实话题解我没看懂...
但是get到了矩乘这个初步思想
于是自己YY了一个方法..
感觉比题解的方法简单
设f[l][i]表示前l个,已经连续i个,如果i<=k,表示前面只有偶数个1,如果i>=k+1,表示前面有奇数个1(这个时候连续的就是i-k-1个)(注意f[l]是一个向量)
然后g[i][j]表示第i个区间,初始的时候已经有j个1了,这个时候的状态矩阵(g[i][j][j][0] = 1,其余元素全为0)
然后转移矩阵就是很显然的:f[i][0~k]往f[i+1][0]转,f[i][j]往f[i+1][j+k-1]转,奇数部分也是一样的
好,现在看怎么处理区间,因为遇到一个区间的时候已经连续了几个都有可能,所以要处理g[i][0~k](只有可能是偶数)
那么可以把区间当成一个子问题递归的搞
搞完区间之后又怎么办呢,只需要令
f[r[i]][j]=sigma(o=0,k)f[l[i]][o]*g[i][o][j][0] (j <= k)
f[r[i]][j]=sigma(o=0,k)f[l[i]][k+1+o]*g[i][o][j][0] (j > k)
(注意区间中的个数必须是偶数)
这样就得到了最后的f
因为总的序列有奇数还是偶数个1是没有限制的,所以最后答案就是sigma(i=0,2*k+1)f[n][i]
----------------------------------------------------------
评论 (0)
