HDU-4055 Number String

Posted on | Edited on | In | Views:

题意

给你一个字符串s，s[i] = ‘D’表示排列中a[i] > a[i+1]，s[i] = ‘I’表示排列中a[i] < a[i+1]。

比如排列 {3, 1, 2, 7, 4, 6, 5} 表示为字符串 DIIDID。

题解

很巧妙的DP做法，$dp[i][j]$表示前i个满足字符串条件的结尾为j的 i 的排列，注意是i的排列，前面并没有数大于i。那又是如何往下递推呢？

如果s[i - 1]是’ I ‘，那么$dp[i][j] = dp[i-1][j-1] + dp[i-1][j-2] + .. + dp[i-1][1]$
如果s[i - 1]是‘D’，那么$dp[i][j] = dp[i-1][j] + dp[i-1][j+1] + … + dp[i-1][i]$，因为要令当前位为j，如果前面出现过j，就令前面的所有大于等于j的数+1，就能构造出新的排列了。

比如{1, 3, 5, 2, 4}，要在第六位插入3,令 >= 3的数都+1，于是就构造出新的 排列{1, 4, 6, 2, 5, 3}。然后代码的话处理出前缀和$sum[i][j]$，就不用$dp[i][j]$了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef __int64 ll;
 
const int maxn = 1000 + 5;
const int mod = 1000000007;
 
ll sum[maxn][maxn];
char s[maxn];
 
int main() {
    while(scanf("%s", s) != -1) {
        int len = strlen(s);
        sum[0][1] = 1;
        for(int i = 1;i <= len; i++) {
            for(int j = 1;j <= i+1; j++) {
                sum[i][j] = sum[i][j-1];
                if(s[i-1] != 'D')
                    sum[i][j] += sum[i-1][j-1];
                if(s[i-1] != 'I')
                    sum[i][j] += sum[i-1][i] - sum[i-1][j-1] + mod;
                sum[i][j] %= mod;
            }
        }
        printf("%I64d\n", sum[len][len+1]);
    }
    return 0;
}

引用

https://blog.csdn.net/jayye1994/article/details/12361481