P1133 教主的花园

    • 461通过
    • 1.1K提交
  • 题目提供者
  • 标签 动态规划,动规,dp
  • 难度 普及+/提高
  • 时空限制 1s / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 推荐的相关题目

    题目描述

    教主有着一个环形的花园,他想在花园周围均匀地种上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一定为偶数。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。