【bzoj1996】[Hnoi2010]chorus 合唱队 区间dp
DP 区间
2023-09-11 14:22:39 时间
题目描述
给出n个互不相同的数,按照某种方式插入到序列中(初始序列为空)。每次插入的数如果大于上一次插入的数则插入到序列最右端,否则插入到序列最左端。现给出最终的序列,求插入的方案数 mod 19650827。
输入
输出
样例输入
4
1701 1702 1703 1704
样例输出
8
题解
区间dp水题
由于每次插入都是往两端插入,因此只需要考虑插入的位置是左端还是右端。
设$f[i][j][k]$表示完成$[i,j]$这段区间,最后插入的位置在左边(0)/右边(1)的方案数。那么考虑除该次插入的位置以外的区间的上一个插入的位置,如果能够满足条件则更新即可。
时间复杂度$O(n^2)$
#include <cstdio> #define N 1010 #define mod 19650827 int a[N] , f[N][N][2]; int main() { int n , k , i , j; scanf("%d" , &n); for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &a[i]) , f[i][i][0] = 1; for(k = 2 ; k <= n ; k ++ ) { for(i = 1 ; i <= n - k + 1 ; i ++ ) { j = i + k - 1; if(a[i] < a[i + 1]) f[i][j][0] = (f[i][j][0] + f[i + 1][j][0]) % mod; if(a[i] < a[j]) f[i][j][0] = (f[i][j][0] + f[i + 1][j][1]) % mod; if(a[j] > a[i]) f[i][j][1] = (f[i][j][1] + f[i][j - 1][0]) % mod; if(a[j] > a[j - 1]) f[i][j][1] = (f[i][j][1] + f[i][j - 1][1]) % mod; } } printf("%d\n" , (f[1][n][0] + f[1][n][1]) % mod); return 0; }
相关文章
- 【分段DP】ABC275 F
- 【区间DP】XOR-pyramid
- 【代码源区间dp】括号序列
- 【BZOJ3590】[Snoi2013]Quare 状压DP
- 合并回文子串(区间DP)
- HDU 6377 度度熊看球赛 (计数DP)
- POJ 3280 Cheapest Palindrome (区间DP)
- HDU 5900 QSC and Master (区间DP)
- px、dp和sp,这些单位有什么区别?
- 刷题心得—拓扑序在图上DP中的应用
- 浅谈区间DP
- ZOJ - 3469 Food Delivery(区间DP)
- POJ3280 Cheapest Palindrome 【DP】
- 【bzoj2669】[cqoi2012]局部极小值 容斥原理+状压dp
- 【bzoj3672】[Noi2014]购票 斜率优化dp+CDQ分治+树的点分治
- 【bzoj4197】[Noi2015]寿司晚宴 分解质因数+状态压缩dp
- 【bzoj1270】[BeijingWc2008]雷涛的小猫 dp
- 【bzoj3831】[Poi2014]Little Bird 单调队列优化dp
- 【bzoj1131】[POI2008]Sta 树形dp
- 【bzoj1742】[Usaco2005 nov]Grazing on the Run 边跑边吃草 区间dp