教主的花园

题目描述

教主有着一个环形的花园，他想在花园周围均匀地种上n棵树，但是教主花园的土壤很特别，每个位置适合种的树都不一样，一些树可能会因为不适合这个位置的土壤而损失观赏价值。

教主最喜欢

输入格式

第一行为一个正整数

接下来 $nn行，每行33个不超过1000010000的正整数a_i,b_i,c_iai,bi,ci，按顺时针顺序表示了第ii个位置种高度为10,20,3010,20,30的树能获得的观赏价值。$

第

输出格式

一个正整数，为最大的观赏价值和。

输入输出样例

输入 #1

输出 #1

说明/提示

【样例说明】

第

【数据规模与约定】

对于 $20\%20%的数据，有n≤10n≤10；$

对于 $40\%40%的数据，有n≤100n≤100；$

对于 $60\%60%的数据，有n≤1000n≤1000；$

对于 $100\%100%的数据，有4≤n≤1000004≤n≤100000，并保证nn一定为偶数。$

$感悟“$

$把教主打死，乱砍乱种$

令f[i][j][k][first]为在第i个位置，本位置选了第j种树，前一个位置选第k种树，第一棵树种的是first时的最大观赏值！

f[i][j][k][first]=(所有y>k<j 或 y<k>j) max(f[i-1][k][y][first]+v[i][j]) ！

然后特殊判断(n-1)位置、n位置、1位置是否满足！

#include<cstdio>
#include<iostream>

using namespace std;

int f[100010][4][4][4];

int v[100010][4];


int i,j,x,y,z,p,l,maxv=0;
int main(){
    int n;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d %d %d",&v[i][1],&v[i][2],&v[i][3]);
    }
    for(i=1;i<4;i++){
        for(j=1;j<4;j++){
            f[0][i][j][i]=v[0][i];
        }
    }
    for(i=1;i<n;i++){
        for(j=1;j<4;j++){
            for(x=1;x<4;x++){
                for(y=1;y<4;y++){
                    for(z=1;z<4;z++){
                        if((y>x&&x<j)||(y<x&&x>j)){
                            f[i][j][x][z]=max(f[i][j][x][z],f[i-1][x][y][z]+v[i][j]);
                        }
                    }
                }
            }
        }
    }
    for(j=1;j<4;j++){
        for(p=1;p<4;p++){
            for(l=1;l<4;l++){
                if((p<j&&j>l)||(p>j&&j<l)){
                    maxv=max(maxv,f[n-1][j][p][l]);
                }
            }
        }
    }
    printf("%d",maxv);
    return 0;
}