洛谷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<=k;i++)
 3 using namespace std ;
 4
 5 const int N = 100011 ;
 6 int n,ans ;
 7 int F1[N],F2[N][2],F3[N],num[N][4] ;
 8
 9 inline int read()
10 {
11     int x = 0 , f = 1 ;
12     char ch = getchar() ;
13     while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) f = -1 ; ch = getchar(); }
14     while(ch>=‘0‘&&ch<=‘9‘) { x = x * 10+ch-48 ; ch = getchar(); }
15     return x * f ;
16 }
17
18 inline void calc()
19 {
20     For(i,2,n) {
21         if( F2[i-1][1] ) F1[i] = max( F1[i],F2[i-1][1]+num[i][1] ) ;
22         if( F3[i-1] )    F1[i] = max( F1[i],F3[i-1]+num[i][1] ) ;
23         if( F2[i-1][0] ) F3[i] = max( F3[i],F2[i-1][0]+num[i][3]) ;
24         if( F1[i-1] )    F3[i] = max( F3[i],F1[i-1]+num[i][3] ) ;
25         if( F1[i-1] )    F2[i][1] = F1[i-1] + num[i][2] ;
26         if( F3[i-1] )    F2[i][0] = F3[i-1] + num[i][2];
27     }
28 }
29
30 int main()
31 {
32     n = read() ;
33     For(i,1,n)
34       num[i][1] = read() ,num[i][2] = read() ,num[i][3] = read() ;
35     For(k,1,4) {
36         memset(F1,0,sizeof F1) ;
37         memset(F2,0,sizeof F2) ;
38         memset(F3,0,sizeof F3) ;
39         if(k==1) F1[ 1 ] = num[ 1 ][ 1 ] ;
40         if(k==2) F2[ 1 ][0] = num[ 1 ][ 2 ] ;
41         if(k==3) F2[ 1 ][1] = num[ 1 ][ 2 ] ;
42         if(k==4) F3[ 1 ] = num[ 1 ][ 3 ] ;
43         calc() ;
44         if(k==1) ans = max(ans,F3[n]), ans = max(ans,F2[n][1]) ;
45         if(k==2) ans = max(ans,F3[n]) ;
46         if(k==3) ans = max(ans,F1[n]) ;
47         if(k==4) ans = max(ans,F1[n]), ans = max(ans,F2[n][0]) ;
48     }
49     printf("%d\n",ans) ;
50     return 0 ;
51 }
时间: 07-18

洛谷P1133 教主的花园 动态规划的相关文章

洛谷P1133 教主的花园

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

洛谷1133 教主的花园

洛谷1133 教主的花园 本题地址:http://www.luogu.org/problem/show?pid=1133 题目描述 教主有着一个环形的花园,他想在花园周围均匀地种上n棵树,但是教主花园的土壤很特别,每个位置适合种的树都不一样,一些树可能会因为不适合这个位置的土壤而损失观赏价值. 教主最喜欢3种树,这3种树的高度分别为10,20,30.教主希望这一圈树种得有层次感,所以任何一个位置的树要比它相邻的两棵树的高度都高或者都低,并且在此条件下,教主想要你设计出一套方案,使得观赏价值之和最

P1133 教主的花园 (动态规划)

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

P1133 教主的花园

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

洛谷P1941 飞扬的小鸟 动态规划

洛谷P1941 飞扬的小鸟 动态规划 这道题主要要注意一下飞到m以上之后高度还是 m 这个就要在判断一下 比较直接暴力的动归 是 O(N^3) f[ i ][ j ] 到 i ,j 这个位置 所需要的最少点击次数 如果不能到,就是无限大 f[ i ][ j ] = min(f[ i-1 ][ j-up[i-1] ] +1 , f[ i-1 ][ j+down[i-1] ] ) 因为可以向上飞无限次 这其实就相当于是无限背包 然后 f[ i ][ j ] 就可以从 f[ i ][ j-up[ i-

洛谷P1450 [HAOI2008]硬币购物 动态规划 + 容斥原理

洛谷P1450 [HAOI2008]硬币购物 动态规划 + 容斥原理 1.首先我们去掉限制 假设 能够取 无数次 也就是说一开始把他当做完全背包来考虑 离线DP 预处理 复杂度 4*v 用f[ i ] 表示 空间 为 i 的方案数 答案ans 其实就是所有方案 - 所有超过限制的方案 限制指的就是题目中限制 某个硬币有几枚 然后所有超过限制的方案用容斥来做 所有超过限制的方案 要减 == -1 超过限制的方案 - 2 超过限制的方案 - 3 超过限制的方案 - 4 超过限制的方案 + 1和2 超

洛谷 P2801 教主的魔法 题解

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

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

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

P1133教主的花园

本题是一道多维DP题目,那么在不打开算法标签的情况下怎么去想呢, 首先是题目的求的是最值,比较好想到的就是动态规划.首先是本题的种植范围限在一维,但是有种类要求,可以把高度10,20,30简单理解为种类1,2,3(因为没有其他奇奇怪怪的东西). 我们需要一维记录位置,二维记录种类,而教主大人又有特殊审美,所以要对树之间进行判断,三维记录前一个树的种类,而植树场地又是一个环,所以...再开一维特判1和n的种类,即记录第一课树的种类.所以...int f[100010][4][4][4],虽然是4维