題意：

給出一個由I、D和？組成的串，串的長度是n，我們要根據串的規則構造出滿足的由1~n+1組成的數列，其中每個數字只出現一次。串的規則定義如下：

如果當前字母是I，我們要保證這一位的數字要比前一位大，如果是D，則比前一位小，？代表都可以。請求出滿足串的規則的數列的個數。

思路：

首先我們構造狀態如下：

dp[i][j]=k 表示我們用1~i這些數字構造前i位且第i位是j的情況數目是k。

同時定義：sum[i][j]=dp[i][1]+dp[i][2]+...+dp[i][j];

很容易想到：如果當前位是I，dp[i][j]=sum[i-1][j-1];

如果當前位是D呢？我們如果用樸素的想法：dp[i][j]=sum[i-1][n]-sum[i-1][j-1],這樣可能會數字填重復，所以我們要換個思路。

很容易想到,如果一個數列是{1,2,3}，如果我們要在末尾插入一個2，數列就會變的不合法，但是如果我們把{1,2,3}中的大于2的數字都加1，這樣數列就變成了{1,3,4}，我們插入2就合法了，所以當當前位是D的時候，我們想到了下面的轉移方程：

dp[i][j]=sum[i-1][i-1]-sum[i-1][j-1];

處理？的時候就兩個都跑一遍，同時要注意同余模，減法的同余模：

（a-b）%mod=（a%mod-b%mod+mod)%mod

因為這個我們還WA了一次。

代碼：

#include <iostream> #include <cstdio> #include <cstring> using namespace std;const long long maxn = 1005; const long long mod = 1000000007;long long dp[maxn][maxn]; char str[maxn]; long long sum[maxn];int main() {while(EOF != scanf("%s",str)) {memset(dp, 0, sizeof(dp));memset(sum, 0, sizeof(sum));sum[1] = 1;dp[1][1] = 1;long long l = strlen(str);long long ans = 0;for(long long i = 2; i <= l + 1; i ++) {if(str[i - 2] == 'I') {for(long long j = 1; j <= i; j++) {dp[i][j] += sum[j - 1];dp[i][j] %= mod;}} else if(str[i - 2] == 'D') {for(long long j = 1; j <= i; j++) {long long tmp = (sum[i - 1] - sum[j - 1] + mod) % mod;dp[i][j] += tmp;dp[i][j] %= mod;}} else {for(long long j = 1; j <= i; j++) {dp[i][j] += sum[j - 1];dp[i][j] %= mod;}for(long long j = 1; j <= i; j++) {long long tmp = (sum[i - 1] - sum[j - 1] + mod) % mod;dp[i][j] += tmp;dp[i][j] %= mod;}}sum[0] = 0;for(long long j = 1; j <= i; j++) {sum[j] = sum[j - 1] + dp[i][j];sum[j] %= mod;}} printf("%lld\n", sum[l + 1]);}return 0; }

總結

以上是生活随笔為你收集整理的uvali5697(DP)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。