bzoj 1996 區間dp

1996: [Hnoi2010]chorus 合唱隊

Time Limit: 4 Sec  Memory Limit: 64 MB

Submit: 1727  Solved: 1115

[​​Submit​​​][​​Status​​​][​​Discuss​​]

Description

Input

Output

Sample Input

4

1701 1702 1703 1704

Sample Output

8

HINT

要想知道[l,r]的初始隊形的方案數，如果我們知道[l,r-1]和[l+1,r]有幾種初始方案的話似乎就可以轉移了，但是還是有點問題，我們如何判斷不在區間裡的那個元素前面的元素的值，根據大或者小往前面或後面插入，如果不知道相對大小似乎不可行，我們可以多開一維記錄最後一個元素的位置，隻有兩種開頭或者結尾。

但要注意初始化時對于dp[i][i][0]和dp[i][i][1]隻要有一個為零就好了，否則會出現重複的轉移，單個元素沒什麼前後之分。

1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define LL long long
 4 #define mod 19650827
 5 int dp[1005][1005][2];
 6 int a[1005];
 7 int f(int l,int r,int x)
 8 {
 9     if(dp[l][r][x]!=-1) return dp[l][r][x];
10     if(l==r)   return x;
11     int res=0;
12     if(x){
13         if(a[r]>a[r-1]) res=(res+f(l,r-1,1));
14         if(a[r]>a[l])   res=(res+f(l,r-1,0));
15     }
16     else{
17         if(a[l]<a[r]) res=(res+f(l+1,r,1));
18         if(a[l]<a[l+1]) res=(res+f(l+1,r,0));
19     }
20     return dp[l][r][x]=res%mod;
21 }
22 int main()
23 {
24     int N,i,j,k,s;
25     scanf("%d",&N);
26     for(i=1;i<=N;++i) scanf("%d",a+i);
27     memset(dp,-1,sizeof(dp));
28     printf("%d\n",(f(1,N,1)+f(1,N,0))%mod);
29     return 0;
30 }