首页 > 题解 > luogu3205 [HNOI2010]CHORUS 合唱队

luogu3205 [HNOI2010]CHORUS 合唱队


luogu题面炸了,可以去bzoj1996看题面

题目描述

输入

输出

样例输入

4

1701 1702 1703 1704

样例输出

8

提示

题解

这是什么DP呢?发现好像加完后区间里面的数值就和没啥关系了,只和第一个数值有关。

这种枚举区间的应该就是区间dp了吧。。

$f[i][j][k]$表示区间$i-j$最后一个放的是$i/j,(k=0/1)$的方案数。

然后枚举就好了,注意要枚举区间长度,才能往下推。

还有$f[i][i][0]=1,f[i][i][1]=0$,如果都是1,就会算重。


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×