洛谷1133 教主的花园

洛谷1133 教主的花园

本题地址:http://www.luogu.org/problem/show?pid=1133

题目描述

教主有着一个环形的花园,他想在花园周围均匀地种上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的树,价值最高。

【思路】

环形DP。

如果这个花园不是环而是直线的话:定义d[i][j]表示到第i棵树且目前第i棵树的状态为j的 最大价值。则有转移方程(见代码)。用到了别人的一个技巧可以定义j==2的时侯树高20且两边的树比他矮,定义j==3的时候树高20且两边的树比他高。这是自己没想到的。

对于环形:枚举第一棵树的高度,DP。最后只考查符合枚举的d。

【代码】

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4
 5 const int maxn = 1000000+10;
 6 const int INF=1<<30;
 7 const int h[]={0,1,2,2,3};
 8 int d[maxn][5],w[maxn][4];
 9 int n;
10
11 int main() {
12     ios::sync_with_stdio(false);
13     cin>>n;
14     for(int i=1;i<=n;i++) cin>>w[i][1]>>w[i][2]>>w[i][3];
15
16     int ans=-INF;
17     for(int d1=1;d1<=4;d1++) {
18         memset(d,0,sizeof(d));
19         for(int i=1;i<=4;i++) d[1][i]=-INF;  //表示不可达
20         d[1][d1] = w[1][h[d1]];
21         for(int i=2;i<=n;i++)
22         {
23                 d[i][1]=max(d[i-1][4],d[i-1][2])+w[i][1];
24                 d[i][2]=d[i-1][1]+w[i][2];
25                 d[i][3]=d[i-1][4]+w[i][2];
26                 d[i][4]=max(d[i-1][1],d[i-1][3])+w[i][3];
27         }
28         switch (d1) {
29              case 1: ans=max(ans,d[n][2]);ans=max(ans,d[n][4]); break;
30              case 2: ans=max(ans,d[n][1]); break;
31              case 3: ans=max(ans,d[n][4]); break;
32              case 4: ans=max(ans,d[n][1]);ans=max(ans,d[n][3]); break;
33         }
34     }
35     cout<<ans;
36     return 0;
37 }
时间: 10-18

洛谷1133 教主的花园的相关文章

洛谷P1133 教主的花园 动态规划

洛谷P1133 教主的花园动态规划 这里是环状的,但是我们并不用将他破环成链 只要枚举第一个点 根据第一个点选择最后一个选择什么就行了 然后我们进行DP注意如果当前是 2 的话要分情况 上一次是上升 1 还是下降 0 F1[ i ] 表示 第 i 位置的种第 1 种树所能获得的最大价值 F2[ i ][ 0 ] 表示 第 i 位置的 种第 2 种树 且上次是下降 1 #include <bits/stdc++.h> 2 #define For(i,j,k) for(int i=j;i<=

洛谷P1133 教主的花园

题目描述 教主有着一个环形的花园,他想在花园周围均匀地种上n棵树,但是教主花园的土壤很特别,每个位置适合种的树都不一样,一些树可能会因为不适合这个位置的土壤而损失观赏价值. 教主最喜欢3种树,这3种树的高度分别为10,20,30.教主希望这一圈树种得有层次感,所以任何一个位置的树要比它相邻的两棵树的高度都高或者都低,并且在此条件下,教主想要你设计出一套方案,使得观赏价值之和最高. 输入输出格式 输入格式: 输入文件garden.in的第1行为一个正整数n,表示需要种的树的棵树. 接下来n行,每行

洛谷 P2801 教主的魔法 题解

此文为博主原创题解,转载时请通知博主,并把原文链接放在正文醒目位置. 题目链接:https://www.luogu.org/problem/show?pid=2801 题目描述 教主最近学会了一种神奇的魔法,能够使人长高.于是他准备演示给XMYZ信息组每个英雄看.于是N个英雄们又一次聚集在了一起,这次他们排成了一列,被编号为1.2.…….N. 每个人的身高一开始都是不超过1000的正整数.教主的魔法每次可以把闭区间[L, R](1≤L≤R≤N)内的英雄的身高全部加上一个整数W.(虽然L=R时并不

洛谷 P2801 教主的魔法

题目描述 教主最近学会了一种神奇的魔法,能够使人长高.于是他准备演示给XMYZ信息组每个英雄看.于是N个英雄们又一次聚集在了一起,这次他们排成了一列,被编号为1.2.…….N. 每个人的身高一开始都是不超过1000的正整数.教主的魔法每次可以把闭区间[L, R](1≤L≤R≤N)内的英雄的身高全部加上一个整数W.(虽然L=R时并不符合区间的书写规范,但我们可以认为是单独增加第L(R)个英雄的身高) CYZ.光哥和ZJQ等人不信教主的邪,于是他们有时候会问WD闭区间 [L, R] 内有多少英雄身高

BZOI——3343: 教主的魔法 || 洛谷—— P2801 教主的魔法

http://www.lydsy.com/JudgeOnline/problem.php?id=3343  ||  https://www.luogu.org/problem/show?pid=2801 题目描述 教主最近学会了一种神奇的魔法,能够使人长高.于是他准备演示给XMYZ信息组每个英雄看.于是N个英雄们又一次聚集在了一起,这次他们排成了一列,被编号为1.2.…….N. 每个人的身高一开始都是不超过1000的正整数.教主的魔法每次可以把闭区间[L, R](1≤L≤R≤N)内的英雄的身高全

洛谷教主花园dp

洛谷-教主的花园-动态规划 题目描述 教主有着一个环形的花园,他想在花园周围均匀地种上n棵树,但是教主花园的土壤很特别,每个位置适合种的树都不一样,一些树可能会因为不适合这个位置的土壤而损失观赏价值. 教主最喜欢3种树,这3种树的高度分别为10,20,30.教主希望这一圈树种得有层次感,所以任何一个位置的树要比它相邻的两棵树的高度都高或者都低,并且在此条件下,教主想要你设计出一套方案,使得观赏价值之和最高. 输入输出格式 输入格式: 输入文件garden.in的第1行为一个正整数n,表示需要种的

洛谷 P2056 BZOJ 2743 [HEOI2012]采花

//表示真的更喜欢洛谷的题面 题目描述 萧芸斓是 Z国的公主,平时的一大爱好是采花. 今天天气晴朗,阳光明媚,公主清晨便去了皇宫中新建的花园采花.花园足够大,容纳了 n 朵花,花有 c 种颜色(用整数 1-c 表示) ,且花是排成一排的,以便于公主采花. 公主每次采花后会统计采到的花的颜色数, 颜色数越多她会越高兴! 同时, 她有一癖好,她不允许最后自己采到的花中,某一颜色的花只有一朵.为此,公主每采一朵花,要么此前已采到此颜色的花,要么有相当正确的直觉告诉她,她必能再次采到此颜色的花. 由于时

洛谷 P2709 BZOJ 3781 小B的询问

题目描述 小B有一个序列,包含N个1~K之间的整数.他一共有M个询问,每个询问给定一个区间[L..R],求Sigma(c(i)^2)的值,其中i的值从1到K,其中c(i)表示数字i在[L..R]中的重复次数.小B请你帮助他回答询问. 输入输出格式 输入格式: 第一行,三个整数N.M.K. 第二行,N个整数,表示小B的序列. 接下来的M行,每行两个整数L.R. 输出格式: M行,每行一个整数,其中第i行的整数表示第i个询问的答案. 输入输出样例 输入样例#1: 6 4 3 1 3 2 1 1 3

洛谷1231 教辅的组成

洛谷1231 教辅的组成 https://www.luogu.org/problem/show?pid=1231 题目背景 滚粗了的HansBug在收拾旧语文书,然而他发现了什么奇妙的东西. 题目描述 蒟蒻HansBug在一本语文书里面发现了一本答案,然而他却明明记得这书应该还包含一份练习题.然而出现在他眼前的书多得数不胜数,其中有书,有答案,有练习册.已知一个完整的书册均应该包含且仅包含一本书.一本练习册和一份答案,然而现在全都乱做了一团.许多书上面的字迹都已经模糊了,然而HansBug还是可