首页 > 代码库 > 洛谷P1133 教主的花园
洛谷P1133 教主的花园
题目描述
教主有着一个环形的花园，他想在花园周围均匀地种上n棵树，但是教主花园的土壤很特别，每个位置适合种的树都不一样，一些树可能会因为不适合这个位置的土壤而损失观赏价值。
教主最喜欢3种树，这3种树的高度分别为10，20，30。教主希望这一圈树种得有层次感，所以任何一个位置的树要比它相邻的两棵树的高度都高或者都低，并且在此条件下，教主想要你设计出一套方案，使得观赏价值之和最高。
输入输出格式
输入格式：
输入文件garden.in的第1行为一个正整数n，表示需要种的树的棵树。
接下来n行，每行3个不超过10000的正整数ai，bi，ci，按顺时针顺序表示了第i个位置种高度为10，20，30的树能获得的观赏价值。
第i个位置的树与第i+1个位置的树相邻，特别地，第1个位置的树与第n个位置的树相邻。
输出格式：
输出文件garden.out仅包括一个正整数，为最大的观赏价值和。
输入输出样例
输入样例#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问题。然而1和n位置会相互影响，导致决策有后效性。
枚举1位置所种的树（只有三种情况），分别DP，再从三种情况的解中取最大值。
设f[位置][该位置种的树][前一位置种的树]=最大收益
决策方法很多，我选择暴力枚举每个决策。具体看代码
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 using namespace std; 9 const int mxn=100010;10 int read(){11 int x=0,f=1;char ch=getchar();12 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}13 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}14 return x*f;15 }16 int n;17 int f[mxn][3][3];//长度，末尾两种树 18 int a[3][mxn];19 int ans=0;20 void DP(int first){//枚举第一棵树 21 memset(f,0,sizeof f);22 int i,j;23 for(i=0;i<3;i++){24 if(i==first)continue;25 f[2][i][first]=a[i][2]+a[first][1];26 }27 for(i=3;i<=n;i++){//枚举位置 28 for(j=0;j<3;j++){//枚举上一位置树的种类 29 if(j==0){//中间是最低的树，两边都需要更高 30 for(int k=1;k<=2;k++)31 f[i][k][0]=max(f[i-1][0][1],f[i-1][0][2])+a[k][i];32 continue;33 }34 if(j==2){//中间是最高的树，两边都需要更低 35 for(int k=0;k<=1;k++)36 f[i][k][2]=max(f[i-1][2][0],f[i-1][2][1])+a[k][i];37 continue;38 }39 if(j==1){//中间是中等的树，两边要么都高要么都低 40 f[i][2][1]=f[i-1][1][2]+a[2][i];41 f[i][0][1]=f[i-1][1][0]+a[0][i];42 }43 }44 }45 //46 switch(first){//根据第1棵树的种类决策第n棵树的种类 47 case 0:{48 int tmp=0;49 for(int k=1;k<=2;k++){50 for(int l=0;l<k;l++)51 tmp=max(f[n][k][l],tmp);52 }53 ans=max(ans,tmp);54 break;55 }56 case 1:{57 int tmp=0;58 tmp=max(f[n][2][1],f[n][2][0]);59 tmp=max(tmp,max(f[n][0][1],f[n][0][2]));60 ans=max(ans,tmp);61 break;62 }63 case 2:{64 int tmp=0;65 for(int k=0;k<=1;k++){66 for(int l=k+1;l<=2;l++)67 tmp=max(f[n][k][l],tmp);68 }69 ans=max(tmp,ans);70 break;71 }72 }73 74 }75 int main(){76 n=read();77 int i,j;78 for(i=1;i<=n;i++){79 a[0][i]=read();a[1][i]=read();a[2][i]=read();80 }81 for(i=0;i<3;i++)DP(i);82 printf("%d\n",ans);83 return 0;84 }
洛谷P1133 教主的花园
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。