[HNOI2010] 合唱队 chorus

标签：区间DP。
题解：

　　首先分析题目，根据题目中的列队方式以及数据范围，我们容易想到O(n2)的算法，也就是区间DP。发现直接dp[L][R]，不能转移，于是添加一个dp[L][R][0/1]，0表示这个区间最后从左边插入，1则表示右边。
　　然后分析从左边插入，上一个数要么是从左的要么是从右的，因为这个数在左，所以都要比他们大才符合条件。故(H[L]<H[L+1]||H[L]<H[R])，符合条件才能转移：dp[L][R][0]=dp[L+1][R][0]*(H[L]<H[L+1])+dp[L+1][R][1]*(H[L]<H[R]);
　　从右边插入类似：(H[R]>H[L]||H[R]>H[R-1])，dp[L][R][1]=dp[L][R-1][0]*(H[R]>H[L])+dp[L][R-1][1]*(H[R]>H[R-1]);
　　然后答案自然就是dp[1][n][0]+dp[1][n][1]了。

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #define LL long long

 using namespace std;

 const int MAXN=,mod=,INF=0x3f3f3f3f;

 int n;

 int H[MAXN],dp[MAXN][MAXN][];

 int gi(){ int res; scanf("%d",&res); return res;}

 int main()

 {

   freopen("chorus.in","r",stdin);

   freopen("chorus.out","w",stdout);

   n=gi();

   for(int i=;i<=n;i++) H[i]=gi();

   for(int i=;i<n;i++)

     {

       if(H[i]<H[i+])

         {

           dp[i][i+][]=;

           dp[i][i+][]=;

         }

     }

   for(int i=;i<n;i++)

     {

       for(int j=;j+i<=n;j++)

         {

           int L=j,R=j+i;

           dp[L][R][]=(dp[L+][R][]*(H[L]<H[L+])+dp[L+][R][]*(H[L]<H[R]))%mod;

           dp[L][R][]=(dp[L][R-][]*(H[R]>H[L])+dp[L][R-][]*(H[R]>H[R-]))%mod;

         }

     }

   printf("%d\n",(dp[][n][]+dp[][n][])%mod);

   return ;

 }

巴特西

[HNOI2010] 合唱队 chorus

最新文章

热门文章