題目描述
教主有着一個環形的花園，他想在花園周圍均勻地種上n棵樹，但是教主花園的土壤很特别，每個位置适合種的樹都不一樣，一些樹可能會因為不适合這個位置的土壤而損失觀賞價值。
教主最喜歡3種樹，這3種樹的高度分别為10,20,30。教主希望這一圈樹種得有層次感，是以任何一個位置的樹要比它相鄰的兩棵樹的高度都高或者都低，并且在此條件下，教主想要你設計出一套方案，使得觀賞價值之和最高。
輸入輸出格式
輸入格式：
第一行為一個正整數n，表示需要種的樹的棵樹。
接下來n行，每行3個不超過1000010000的正整數a_i,b_i,c_i，按順時針順序表示了第ii個位置種高度為10,20,30的樹能獲得的觀賞價值。
第i個位置的樹與第i+1個位置的樹相鄰，特别地，第1個位置的樹與第n個位置的樹相鄰。
輸出格式：
一個正整數，為最大的觀賞價值和。
輸入輸出樣例
輸入樣例#1：
4
1 3 2
3 1 2
3 1 2
3 1 2
輸出樣例#1：
11 說明
【樣例說明】
第1至n個位置分别種上高度為20,10,30,10的樹，價值最高。
【資料規模與約定】
對于20%的資料，有n≤10；
對于40%的資料，有n≤100；
對于60%的資料，有n≤1000；
對于100%的資料，有4≤n≤100000，并保證n一定為偶數。
分析：
本題較為麻煩，主要原因還是二維DP無法轉移，需要擴充為較為少見的三維DP。
狀态轉移方程是：
f[j][0][0]=max(f[j-1][1][1],f[j-1][2][1])+a[j][0];
f[j][1][0]=f[j-1][2][1]+a[j][1];
f[j][1][1]=f[j-1][0][0]+a[j][1];
f[j][2][1]=max(f[j-1][1][0],f[j-1][0][0])+a[j][2];
CODE:
1 #include<cmath>
2 #include<cstdio>
3 #include<cstring>
4 #include<iostream>
5 #include<algorithm>
6 using namespace std;
7 int n;
8 int a[100005][3];
9 int f[100005][3][2];
10 int ans;
11 inline int get(){
12 char c=getchar();
13 int res=0;
14 while (c<\'0\'||c>\'9\') c=getchar();
15 while (c>=\'0\'&&c<=\'9\'){
16 res=(res<<3)+(res<<1)+c-\'0\';
17 c=getchar();
18 }
19 return res;
20 }
21 int main(){
22 n=get();
23 for(int i=1;i<=n;i++){
24 a[i][0]=get();
25 a[i][1]=get();
26 a[i][2]=get();
27 }
28 for(int i=0;i<3;i++){
29 for(int j=0;j<3;j++){
30 for(int k=0;k<2;k++){
31 f[1][j][k]=0;
32 }
33 }
34 f[1][i][0]=f[1][i][1]=a[1][i];
35 for(int j=2;j<=n;j++){
36 f[j][0][0]=max(f[j-1][1][1],f[j-1][2][1])+a[j][0];
37 f[j][1][0]=f[j-1][2][1]+a[j][1];
38 f[j][1][1]=f[j-1][0][0]+a[j][1];
39 f[j][2][1]=max(f[j-1][1][0],f[j-1][0][0])+a[j][2];
40 }
41 for(int j=0;j<i;j++) ans=max(ans,f[n][j][0]);
42 for(int j=2;j>i;j--) ans=max(ans,f[n][j][1]);
43 }
44 printf("%d\n",ans);
45 return 0;
46 }