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

1996: [Hnoi2010]chorus 合唱队

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

Description

Input

Output

Sample Input

4
1701 1702 1703 1704

Sample Output

HINT

Source

[Submit][Status][Discuss]

HOME Back

最讨厌统计方案数什么的了！

但是这道题确实比较水QAQ 我们发现放数的过程实际上是区间不断向两边延伸的过程，每次更新区间当前的数只有可能是头和尾。于是想到区间DP。

状态$f[i][j][0/1]$表示$i$到$j$区间，当前放的数在头（0）还是尾（1），如果是头就是$i$，要和$i+1$和$j$比较一下更新$dp[i][j][0]$，如果是尾就是$j$，要和$i$和$j-1$比较一下更新$dp[i][j][1]$，转移还是比较显然。

【注意】初始化时只能把$dp[i][i][0]$或$dp[i][i][1]$其中一个赋值，如果两个都赋会导致后来的状态多出来。（长度为2时既可以更新头也可以更新尾

#include<cstdio>
#include<iostream>
#define LL long long
#define MOD 19650827
using namespace std;

int n, a[1005];
int f[1005][1005][2];

int main ( ) {
    scanf ( "%d", &n );
    for ( int i = 1; i <= n; i ++ )    scanf ( "%d", &a[i] ), f[i][i][0] = 1;
    for ( int len = 2; len <= n; len ++ )
        for ( int i = 1; i <= n - len + 1; i ++ ) {
            int j = i + len - 1;
            if ( a[j] > a[j-1] ) f[i][j][1] = ( f[i][j][1] + f[i][j-1][1] ) % MOD;
            if ( a[j] > a[i] ) f[i][j][1] = ( f[i][j][1] + f[i][j-1][0] ) % MOD;
            if ( a[i] < a[j] ) f[i][j][0] = ( f[i][j][0] + f[i+1][j][1] ) % MOD;
            if ( a[i] < a[i+1] ) f[i][j][0] = ( f[i][j][0] + f[i+1][j][0] ) % MOD;
        }
    printf ( "%d", ( f[1][n][0] + f[1][n][1] ) % MOD );
    return 0;
}