P3205 [HNOI2010]合唱队

【题意描述】

给定一串序列，问有多少种初始序列经过如题操作可以得到此序列。

【分析】

我其实是想刷区间 dp 题才看这道题的，，，， 我们知道这是一道区间 dp 题，那么状态转移方程该怎么写呢？

当我们没有想到如何枚举区间处理的时候，我们首先可以先联想到以前做过的 dp 题。

这道题是要我们向左向右插入数字，这让我想起了p2858奶牛的零食。

来看一看~~

那么我们可以归纳出左端点的数只与下一个或者右端点的在初始序列中相邻，右端点的数只与前一个或者左端点的在初始序列中相邻。

我们可以定义 f[ i ][ j ][ k ]为 i 到 j 这一段将 i 或 j 插入的情况数， k = 1 表示在右端插入， k = 0 在左端插入。因为每一次的插入位置只与上一个数有关，那么我们只要分出 4 种情况进行讨论即可。

1. 当右端点的数大于上一个且上一个插入在右端时：

   f[ i ][ j ][ 1 ] += f[ i ][j - 1][ 1 ];

2. 当右端点的数大于左端点且上一个插入在左端时：

   f[ i ][ j ][ 1 ] += f[ i ][ j - 1 ][ 0 ];

3. 当左端点的数小于后一个且上一个插入在左端时：

   f[ i ][ j ][ 0 ] += f[ i + 1 ][ j ][ 0 ];

4. 当左端点的数小于右端点且上一个插入在右端时：

   f[ i ][ j ][ 0 ] += f[ i + 1 ][ j ][ 1 ];

【核心代码】

注意答案为最后一个插入的为右端点和最后一个插入的为左端点之和。还有千万别忘了取模！！！！

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

【正解】

#include <bits/stdc++.h>
#define N 2001
#define MOD 19650827
using namespace std;

int n;
int a[N];
int f[N][N][2];

inline int read()
{
    char ch = getchar();
    int x = 0, f = 1;
    while(ch > '9' || ch < '0')
    {
        if(ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

void Solve()
{
    for(int i = 1; i <= n; i++)
        f[i][i][0] = 1;
    for(int l = 2; l <= n; l++)
    {
        for(int i = 1; i <= n - l + 1; i++)
        {
            int j = i + l - 1;
            if(a[j] > a[j - 1])
                f[i][j][1] += f[i][j - 1][1];
            if(a[j] > a[i])
                f[i][j][1] += f[i][j - 1][0];
            if(a[i] < a[i + 1])
                f[i][j][0] += f[i + 1][j][0];
            if(a[i] < a[j])
                f[i][j][0] += f[i + 1][j][1];
            f[i][j][0] %= MOD;
            f[i][j][1] %= MOD; 
        }
    }
    printf("%d", (f[1][n][0] + f[1][n][1]) % MOD);
}

int main()
{
    n = read();
    for(int i = 1; i <= n; i++)
        a[i] = read();
    Solve();

    return 0;
}