P1133 教主的花园 dp-白红宇

P1133 教主的花园 dp

阅读量：4323 次

发布时间：2019-06-06

本文共 1822 字，大约阅读时间需要 6 分钟。

题目描述

教主有着一个环形的花园，他想在花园周围均匀地种上n棵树，但是教主花园的土壤很特别，每个位置适合种的树都不一样，一些树可能会因为不适合这个位置的土壤而损失观赏价值。

教主最喜欢

输入输出格式

输入格式：

第一行为一个正整数

接下来 $nn行，每行33个不超过1000010000的正整数a_i,b_i,c_iai,bi,ci，按顺时针顺序表示了第ii个位置种高度为10,20,3010,20,30的树能获得的观赏价值。$

第

输出格式：

一个正整数，为最大的观赏价值和。

输入输出样例

输入样例#1：

4 1 3 2 3 1 2 3 1 2 3 1 2

输出样例#1：

说明

【样例说明】

第

【数据规模与约定】

对于 $20\%20%的数据，有n≤10n≤10；$

对于 $40\%40%的数据，有n≤100n≤100；$

对于 $60\%60%的数据，有n≤1000n≤1000；$

对于 $100\%100%的数据，有4≤n≤1000004≤n≤100000，并保证nn一定为偶数。$

$挺好的一道dp$

$一开始开了三维的 dp[i][j][k] 表示前i个最后一个为k 前一个为j 的最大价值然后向后递推$

$只有70分因为首尾不一定满足$

然后再开一维记录首的高度即可

最后再判断一下最后一个数是否满足 (因为知道倒数第二个和第一个）

但是还不知道首是否满足条件

题目还给了一个关键条件 n为偶数这样一来 n-1个点满足了条件剩下一个也必然满足条件

#include
      
       using namespace std;//input by bxd#define rep(i,a,b) for(int i=(a);i<=(b);i++)#define repp(i,a,b) for(int i=(a);i>=(b);--i)#define RI(n) scanf("%d",&(n))#define RII(n,m) scanf("%d%d",&n,&m)#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)#define RS(s) scanf("%s",s);#define ll long long#define pb push_back#define REP(i,N)  for(int i=0;i<(N);i++)#define CLR(A,v)  memset(A,v,sizeof A)//#define inf 0x3f3f3f3fconst int N=100000+5;ll dp[N][3][3][3];int n;struct node{    int v[4];}ss[N];int main(){    RI(n);    rep(i,1,n)    RIII(ss[i].v[1],ss[i].v[2],ss[i].v[3]);    ss[n+1]=ss[1];    rep(i,1,3)    rep(j,1,3)    if(i!=j)    dp[2][i] [i][j]=ss[1].v[i]+ss[2].v[j];    rep(i,3,n+1)    {        rep(fi,1,3)        rep(j,1,3)//当前        rep(s,1,3)//前一位        rep(k,1,3)//再前一位        {            if(j>s&&k>s||j
       
        
         k&&j>k )    ans=max(ans,dp[n][i][j][k] );    cout<

View Code

转载于:https://www.cnblogs.com/bxd123/p/10862889.html

你可能感兴趣的文章

《小强升职记——时间管理故事书》读书笔记