1996: [Hnoi2010]chorus 合唱队
Time Limit: 4 Sec Memory Limit: 64 MBSubmit: 1853 Solved: 1200
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
4
1701 1702 1703 1704
1701 1702 1703 1704
Sample Output
8
HINT
Source
简单区间dp
1 #include<iostream> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cstdio> 5 #include<cmath> 6 #include<algorithm> 7 #include<queue> 8 #define LL long long 9 #define mod 19650827 10 using namespace std; 11 int read() { 12 char ch=getchar();int x=0,f=1; 13 while(!isdigit(ch)){ch=getchar();} 14 while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();} 15 return x; 16 } 17 int n; 18 int f[1001][1001][2]; 19 int a[1001]; 20 int main() { 21 scanf("%d",&n); 22 for(int i=1;i<=n;i++) scanf("%d",&a[i]); 23 for(int i=1;i<=n;i++) f[i][i][0]=1; 24 for(int j=1;j<=n;j++) { 25 for(int i=1;i+j<=n;i++) { 26 int k=i+j; 27 if(a[i]<a[k]) f[i][k][0]+=f[i+1][k][1]; 28 if(a[i]<a[i+1]) f[i][k][0]+=f[i+1][k][0]; 29 if(a[k]>a[i]) f[i][k][1]+=f[i][k-1][0]; 30 if(a[k]>a[k-1]) f[i][k][1]+=f[i][k-1][1]; 31 f[i][k][1]%=mod;f[i][k][0]%=mod; 32 } 33 } 34 printf("%d",(f[1][n][0]+f[1][n][1])%mod); 35 }