题解 P1133 【教主的花园】

· · 题解

这道题题意还是简单明了的，就是求一种和最大的序列，满足其对应高度(s)wswswsws......

20分很容易想，就是枚举N个位置的10,20,30三种情况，时间复杂度O（3^n），但我们不用每次都枚举3个状态，除了上次的状态还有2个状态，所以时间复杂度O（2^n）然并卵

说实话，我也不知道40分和60分有什么用..........

好了入正题100分

#DP#

第一次想f[i][j][k]表示第i个位置高度为j的最大观赏值，k=1则第j位比第j-1位大，k=2则第j位比第j-1位小，于是就有了以下程序：

#include<bits/stdc++.h>
using namespace std;
const int one=10,two=20,three=30;
int a[100050],b[100050],c[100050],f[100050][40][4],n,m,i,j,k,l,s;
int xiao(int x,int y){
    if(x>y)x=y;
    return x;
}
int da(int x,int y){
    if(x<y)x=y;
    return x;
}
int main(){
    cin>>n;
    for(i=1;i<=n;i++){
        scanf("%d%d%d",&a[i],&b[i],&c[i]);
    }
    memset(f,0,sizeof(f));
    for(i=1;i<=n;i++){
        f[i][one][2]=da(f[i-1][two][1],f[i-1][three][1])+a[i];
        f[i][two][1]=b[i]+f[i-1][one][2];
        f[i][two][2]=b[i]+f[i-1][three][1];
        f[i][three][1]=c[i]+da(f[i-1][one][2],f[i-1][two][2]);
        //cout<<f[i][one][1]<<" "<<f[i][one][2]<<" "<<f[i][two][1]<<" "<<f[i][two][2]<<" "<<f[i][three][1]<<" "<<f[i][three][2]<<endl;

    }
    s=0;
    s=da(s,f[n][one][1]);
    s=da(s,f[n][one][2]);
    s=da(s,f[n][two][1]);
    s=da(s,f[n][two][2]);
    s=da(s,f[n][three][1]);
    s=da(s,f[n][three][2]);
    cout<<s<<endl; 
    return 0;
}

而我还很煞笔的把第二位做成10，20，30............

交完程序，woc70！！！！！！！！！！

表示震惊。

思（瞄）考（了）了（眼）一（题）下（解），原来还是环形。

默默地加了一维，表示第一次选的是10/20/30

终于A了

代码

#include<bits/stdc++.h>
using namespace std;
const int one=1,two=2,three=3;
int a[100050],b[100050],c[100050],f[100050][4][4][4],n,m,i,j,k,l,s;
int xiao(int x,int y){
    if(x>y)x=y;
    return x;
}
int da(int x,int y){
    if(x<y)x=y;
    return x;
}
int main(){
    cin>>n;
    for(i=1;i<=n;i++){
        scanf("%d%d%d",&a[i],&b[i],&c[i]);
    }
    memset(f,0,sizeof(f));
    f[1][one][2][one]=a[1];
    f[1][two][1][two]=b[1];
    f[1][two][2][two]=b[1];
    f[1][three][1][three]=c[1];
    for(i=2;i<=n;i++){
        for(j=1;j<=3;j++){
            f[i][one][2][j]=da(f[i-1][two][1][j],f[i-1][three][1][j])+a[i];
            f[i][two][1][j]=b[i]+f[i-1][one][2][j];
            f[i][two][2][j]=b[i]+f[i-1][three][1][j];
            f[i][three][1][j]=c[i]+da(f[i-1][one][2][j],f[i-1][two][2][j]);
        }
        //cout<<f[i][one][1]<<" "<<f[i][one][2]<<" "<<f[i][two][1]<<" "<<f[i][two][2]<<" "<<f[i][three][1]<<" "<<f[i][three][2]<<endl;
    }

    s=0;
    s=da(s,f[n][one][2][two]);
    s=da(s,f[n][one][2][three]);
    s=da(s,f[n][two][1][one]);
    s=da(s,f[n][two][2][three]);
    s=da(s,f[n][three][1][one]);
    s=da(s,f[n][three][1][two]);
    cout<<s<<endl; 
    return 0;
}

说实话，我对这个鬼畜的转移是怎么改出来的都是懵逼的。

还有为什么我要打one，two，three呀！！！！！！！！！！！！！！！！！！！！！！！！！！！！

气人。。。但还是祝大家AC愉快