贵州省都匀市网站建设,百姓网地址怎么创建,建站流程新手搭建网站第一步,人才网站的会计账如何做链接#xff1a;
1388. 3n 块披萨
题意#xff1a;
一个长度3n的环#xff0c;选n次数字#xff0c;每次选完以后相邻的数字会消失#xff0c;求选取结果最大值
解#xff1a;
这波是~~#xff08;ctrl#xff09;CV工程师了~~
核心思想是选取n个不相邻的元素一定…链接
1388. 3n 块披萨
题意
一个长度3n的环选n次数字每次选完以后相邻的数字会消失求选取结果最大值
解
这波是~~ctrlCV工程师了~~
核心思想是选取n个不相邻的元素一定合法我推不出来猜一猜倒是可以O.o
DP[i][j]表示从[0,i]中选取j个数字的最大值
初始条件我们可以确定如果选择0个数字j0则结果为0如果ji1,则要在不足的数字中进行选取我们设为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个不相邻的数字就能满足题意就很好写了
实际代码
#includebits/stdc.h
using namespace std;
int solve(vectorint temp)
{int numtemp.size(),need(num1)/3;vectorvectorintdp(num,vectorint(need1,0));dp[0][1]temp[0];dp[1][1]max(temp[0],temp[1]);for(int i2;inum;i){for(int j1;jneed;j){dp[i][j] max(dp[i - 1][j],dp[i - 2][j - 1]temp[i]);}}return dp[num-1][need];
}
int maxSizeSlices(vectorint slices)
{int lgslices.size();vectorint v1(slices.begin() 1, slices.end());vectorint v2(slices.begin(), slices.end() - 1);return max(solve(v1),solve(v2));
}
int main()
{vectorint slices;int slice;while(cinslice) slices.push_back(slice);int ansmaxSizeSlices(slices);coutansendl;return 0;
}限制
1 slices.length 500slices.length % 3 01 slices[i] 1000
