題目描述

教主有著一個環形的花園，他想在花園周圍均勻地種上n棵樹，但是教主花園的土壤很特別，每個位置適合種的樹都不一樣，一些樹可能會因為不適合這個位置的土壤而損失觀賞價值。

教主最喜歡 3種樹，這3種樹的高度分別為 10,20,30。教主希望這一圈樹種得有層次感，所以任何一個位置的樹要比它相鄰的兩棵樹的高度都高或者都低，并且在此條件下，教主想要你設計出一套方案，使得觀賞價值之和最高。

輸入輸出格式

輸入格式：

第一行為一個正整數 n ，表示需要種的樹的棵樹。

接下來 n 行，每行 3 個不超過 10000的正整數 \[a_i,b_i,c_i\] ，按順時針順序表示了第 i 個位置種高度為 10,20,30 的樹能獲得的觀賞價值。

第 i個位置的樹與第 i+1 個位置的樹相鄰，特別地，第 1 個位置的樹與第 n 個位置的樹相鄰。

輸出格式：

一個正整數，為最大的觀賞價值和。

輸入輸出樣例

輸入樣例#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 一定為偶數。

Solution

這道題的思路蠻好想的,只是稍微多了一些限制條件.

狀態定義:
\[f[i][j][k]\]
表示當前 i 這個點, i-1 的選擇為 j , 然后 i 的選擇為 k.

狀態轉移
枚舉當前這個的點的 j 和 k,然后判斷 j 和 k 的大小關系.
如 : \[ f[i][j][k] \]其中 j>k
則有前驅狀態:
\[f[i-1][1...j-1][j]\]
其他亦可依次類推.

但是需要注意最后一個節點和第一個節點的大小關系區分.
為此,我們可以直接枚舉一重 head.
然后在里面循環的時候注意判斷最后一個節點即可.

代碼

#include<bits/stdc++.h> using namespace std; const int maxn=100008; int f[maxn][4][4]; int c[maxn][4],n; int ans=-1,head; int main() {ios::sync_with_stdio(false);cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=3;j++)cin>>c[i][j];for(head=1;head<=3;head++){memset(f,0,sizeof(f));f[2][head][1]=c[1][head]+c[2][1];f[2][head][2]=c[1][head]+c[2][2];f[2][head][3]=c[1][head]+c[2][3];for(int i=3;i<=n;i++){for(int j=1;j<=3;j++)for(int k=1;k<=3;k++){if(j==k)continue;else{if(i==n){if(k==head)continue;if(j>k&&k>head)continue;if(j<k&&k<head)continue; }if(j>k)for(int l=1;l<j;l++)f[i][j][k]=max(f[i][j][k],f[i-1][l][j]+c[i][k]);elsefor(int l=j+1;l<=3;l++)f[i][j][k]=max(f[i][j][k],f[i-1][l][j]+c[i][k]);}} }for(int i=1;i<=3;i++)for(int j=1;j<=3;j++)ans=max(f[n][i][j],ans);}cout<<ans<<endl;return 0; }

轉載于:https://www.cnblogs.com/Kv-Stalin/p/9123197.html

總結

以上是生活随笔為你收集整理的P1133 教主的花园 (动态规划)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。