BZOJ 1996 合唱队(DP)-白红宇

BZOJ 1996 合唱队(DP)

阅读量：5076 次

发布时间：2019-06-12

本文共 1498 字，大约阅读时间需要 4 分钟。

考虑从最后的队形开始依次还原最初的队形。

对于当前的队形，要么选最左边的，要么选最右边的。如果选了左边的，那么下次选择的一定是大于它的。右边的同理。

所以定义dp[mark][l][r]为区间[l,r]的选择状态为mark的方法数。

然后记忆化搜索一下就可以了。

# include 
      
       # include 
       
        # include 
        
         # include 
         
          # include 
          
           # include 
           
            # include 
            
             # include 
             # include 
              
               # include 
               
                # include 
                
                 using namespace std;# define lowbit(x) ((x)&(-x))# define pi 3.1415926535# define eps 1e-9# define MOD 19650827# define INF 1000000000# define mem(a,b) memset(a,b,sizeof(a))# define FOR(i,a,n) for(int i=a; i<=n; ++i)# define FO(i,a,n) for(int i=a; i
                 
                   PII;typedef vector
                  
                    VI;# pragma comment(linker, "/STACK:1024000000,1024000000")typedef long long LL;int Scan() { int res=0, flag=0; char ch; if((ch=getchar())=='-') flag=1; else if(ch>='0'&&ch<='9') res=ch-'0'; while((ch=getchar())>='0'&&ch<='9') res=res*10+(ch-'0'); return flag?-res:res;}void Out(int a) { if(a<0) {putchar('-'); a=-a;} if(a>=10) Out(a/10); putchar(a%10+'0');}const int N=1005;//Code begin...int dp[2][N][N], a[N];int dfs(int mark, int l, int r){ if (~dp[mark][l][r]) return dp[mark][l][r]; if (l==r) return dp[mark][l][r]=1; int res=0; if (mark) { if (a[l]
                   
                    a[l]) res+=dfs(1,l+1,r); if (l+1!=r&&a[l+1]>a[l]) res+=dfs(0,l+1,r); } return dp[mark][l][r]=res%MOD;}int main (){ mem(dp,-1); int n; scanf("%d",&n); FOR(i,1,n) scanf("%d",a+i); printf("%d\n",(dfs(0,1,n)+dfs(1,1,n))%MOD); return 0;}