bzoj1996: [Hnoi2010]chorus 合唱队【区间dp】

1996: [Hnoi2010]chorus 合唱队

Time Limit:4 SecMemory Limit:64 MB
Submit:2088Solved:1371
[Submit][Status][Discuss]

Description

Input

Output

Sample Input

4
1701 1702 1703 1704

Sample Output

HINT

emmmm这道题是一道区间dp （因为前天考试区间dp裸题没搞出来这两天做了不少）

看到题目可以考虑到一个显然的性质每次插入数字进去的时候要不是在队头要不是在队尾

那么就可以定义一个状态 $dp[i][j][0/1]$ 表示区间$[i,j]$ 最后一个元素插在队头 / 队尾的方案数

那么初值是什么呢按照第一想法$dp[i][i][0] = dp[i][i][1] = 1$ 实则不然

仔细考虑一下这个初值是错误的因为每次插入要不是插在队头要不是队尾

而这样的含义是我既插在队头又插在队尾不符合题目条件那么这样子转移也是错误的

每次会被多计算一遍

方程式比较好推的用刷表每次判断我这个新元素的位置与上一次的元素比较如果合法方案就加上就可以了

代码

#include <bits/stdc++.h>
using namespace std;

const int mod = 19650827;
int n,dp[1005][1005][2],ans,a[1005];

void solve( ) {
    
    for(int i = 1;i <= n;i ++) dp[i][i][0] = 1;
    for(int len = 1;len <= n;len ++) {
        for(int i = 1;i + len - 1 <= n;i ++) {
            int l = i + len - 1;
            if(i - 1 >= 1) {
                dp[i-1][l][0] = (dp[i-1][l][0] + dp[i][l][0] * (a[i-1] < a[i])) % mod;
                dp[i-1][l][0] = (dp[i-1][l][0] + dp[i][l][1] * (a[i-1] < a[l])) % mod;
            }
            if(l + 1 <= n) {
                dp[i][l+1][1] = (dp[i][l+1][1] + dp[i][l][0] * (a[i] < a[l+1])) % mod;
                dp[i][l+1][1] = (dp[i][l+1][1] + dp[i][l][1] * (a[l] < a[l+1])) % mod;
            }
        }
    }
    ans = (dp[1][n][0] + dp[1][n][1]) % mod;
    printf("%d",ans);
}

int main( ) {
    
    scanf("%d",& n);
    for(int i = 1;i <= n;i ++) scanf("%d",& a[i]);
    solve( );
}

优质内容筛选与推荐>>
1、2.网站的运行原理
2、AML 文件读取
3、计算工作日之后N天的日期
4、环境准备(hadoop_02)
5、UI_UIImageView 基本操作

0 │ 收藏 │ 举报