题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=4055
题目大意
给定连续的1~n的序列,连续两个数字之间为递增关系则用”I”表示,为递减关系则用”D”表示,”?”表示不确定的关系。给定字母序列,求满足该字母关系序列的可能的情况数量。
思想
这个题首先需要考虑用什么表示DP的状态
我们用dp[i][j]表示一段长度为i的、以j为结尾的序列的、满足当前字母关系的情况数量。
则最终答案为sigma{dp[n][i]},1<=i<=n。
该题有一个巧妙地思想:
我们现在要求长度为i的以j结尾的情况数量,那么对于长度为i-1的序列来说,相当于把i插进去并且把j放到最后一个。我们可以这样操作:将i-1的序列中大于等于j的数字都分别+1,其他不变,此时大小关系并没变,则i-1变成了i,j就没有了,顺理成章地放到最后作为末尾元素。
所以我们发现,以j为末尾元素,从长度为i-1到长度为i,我们可以保持前i-1个之间的大小关系不变,只需要考虑最后两个元素间的关系。
所以我们可以得到:
对于”I”:dp[i][j]=sigma{dp[i-1][x]},1<=x<=j-1
对于”D”:dp[i][j]=sigma{dp[i-1][x]},j<=x<=i-1
再用前缀和的优化,即可实现。
一维前缀和优化即:用sum[n]表示前n个元素的和(sigma{elem[i]},1<=i<=n),则sigma{elem[i],left<=i<=right}=sum[right]-sum[left-1]
在该题中,sum[i][j]表示长度为i的序列中,末尾元素为1……j的情况之和,即sigma{dp[i][x]},1<=x<=j
本质是对第二维的一维优化。
代码
1 |
|
后记
对dp的练习还需要进一步加强。学就学,玩就玩,回去看剧去咯~