鏈接：

1388. 3n 塊披薩

題意：

一個長度3n的環，選n次數字，每次選完以后相鄰的數字會消失，求選取結果最大值

解：

這波是~~（ctrl）CV工程師了~~

核心思想是選取n個不相鄰的元素一定合法，我推不出來，猜一猜倒是可以O.o

DP[i][j]表示從[0,i]中選取j個數字的最大值

初始條件，我們可以確定，如果選擇0個數字j==0則結果為0；如果j<i+1,，則要在不足的數字中進行選取，我們設為0（官方是設為INT_MIN，我寫了0好像也沒事，可能是數據弱了？）；由于思想中只對相鄰數字做判斷，所以我們提供[0,0]和[0,1]選取1個數字的值作為DP的初始條件之一，即dp[0][1]=temp[0] 和 dp[1][1]=max(temp[0],temp[1])

剩下的就很簡單了，狀態轉移就是從小的范圍推導出大的范圍，少的選取推導出多的選取，每個DP[I][J]只需要判斷I選不選就行

特別注意的是，由于整體成環狀，所以分別對去掉頭和去掉尾進行一次DP（因為只考慮相鄰）

只要能推出取n個不相鄰的數字就能滿足題意就很好寫了

實際代碼：

#include<bits/stdc++.h>
using namespace std;
int solve(vector<int>& temp)
{int num=temp.size(),need=(num+1)/3;vector<vector<int>>dp(num,vector<int>(need+1,0));dp[0][1]=temp[0];dp[1][1]=max(temp[0],temp[1]);for(int i=2;i<num;i++){for(int j=1;j<=need;j++){dp[i][j] = max(dp[i - 1][j],dp[i - 2][j - 1]+temp[i]);}}return dp[num-1][need];
}
int maxSizeSlices(vector<int>& slices)
{int lg=slices.size();vector<int> v1(slices.begin() + 1, slices.end());vector<int> v2(slices.begin(), slices.end() - 1);return max(solve(v1),solve(v2));
}
int main()
{vector<int> slices;int slice;while(cin>>slice) slices.push_back(slice);int ans=maxSizeSlices(slices);cout<<ans<<endl;return 0;
}

限制：

• 1 <= slices.length <= 500
• slices.length % 3 == 0
• 1 <= slices[i] <= 1000