【动态规划】mr368-教主种树

【题目大意】

【思路】

f[i][0..3]分别表示前i棵树的最大观赏价值总和。

f[i][0]当前树高度为10，且前后的树高度均大于它（这是必然的）；

f[i][1]当前树高度为20，且前后的树高度均大于它；

f[i][2]当前树高度为20，且前后的树高度均小于它；

f[i][3]当前树高度为30，且前后树的高度均小于它（这也是必然的）。

接下来以上述四种情况为第一棵树进行四次dp，每一次的f[i]=max(f[n-1][上述情况对应的前一棵树的情况])，绕各树一圈直到返回起始点，如f[i][0]对应的前一棵树就是f[i-1][2]和f[i-1][3]。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 const int MAXN=+;

 using namespace std;

 int f[MAXN][];

 /*f[i][0..3]·Ö±ð±íʾǰi¿ÃÊ÷µÄ×î´ó¹ÛÉͼÛÖµ×ܺÍ

 f[i][0]µ±Ç°Ê÷¸ß¶ÈΪ10£¬ÇÒÇ°ºóµÄÊ÷¸ß¶È¾ù´óÓÚËü£¨ÕâÊDZØÈ»µÄ£©

 f[i][1]µ±Ç°Ê÷¸ß¶ÈΪ20£¬ÇÒÇ°ºóµÄÊ÷¸ß¶È¾ù´óÓÚËü

 f[i][2]µ±Ç°Ê÷¸ß¶ÈΪ20£¬ÇÒÇ°ºóµÄÊ÷¸ß¶È¾ùСÓÚËü

 f[i][3]µ±Ç°Ê÷¸ß¶ÈΪ30£¬ÇÒÇ°ºóÊ÷µÄ¸ß¶È¾ùСÓÚËü£¨ÕâÒ²ÊDZØÈ»µÄ£©*/

 int a[MAXN][];

 /*a[i][j]±íʾµÚi¸öλÖõÚjÖÖÊ÷µÄÉóÃÀ¼ÛÖµ*/

 int n,ans;

 void init()

 {

     scanf("%d",&n);

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

         for (int j=;j<;j++) scanf("%d",&a[i][j]);

 }

 void dp(int x)

 {

     for (int i=;i<;i++) f[][i]=-0x7fffffff;

     f[][x]=a[][(x+)/];

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

     {

         f[i][]=max(f[i-][],f[i-][])+a[i][];

         f[i][]=f[i-][]+a[i][];

         f[i][]=f[i-][]+a[i][];

         f[i][]=max(f[i-][],f[i-][])+a[i][];

     }

 }

 void mainprocess()

 {

     ans=-;

     dp();

     ans=max(ans,max(f[n-][],f[n-][]));

     dp();

     ans=max(ans,f[n-][]);

     dp();

     ans=max(ans,f[n-][]);

     dp();

     ans=max(ans,max(f[n-][],f[n-][]));

     cout<<ans<<endl;

 }

 int main()

 {

     freopen("mr368.in0","r",stdin);

     freopen("mr368.ou0","w",stdout);

     init();

     mainprocess();

     return ;

 }