当前位置：首页 > news >正文

区间动态规划——【# P3146 [USACO16OPEN] 248 G】

news 2026/5/9 2:39:29

P3146 [USACO16OPEN] 248 G

题目描述

贝西喜欢在手机上下载游戏来玩，尽管她确实觉得对于自己巨大的蹄子来说，小小的触摸屏用起来相当笨拙。

她对当前正在玩的这个游戏特别感兴趣。游戏开始时给定一个包含NNN个正整数的序列（2≤N≤2482 \leq N \leq 2482≤N≤248），每个数的范围在1…401 \ldots 401…40之间。在一次操作中，贝西可以选择两个相邻且相等的数，将它们替换为一个比原数大111的数（例如，她可以将两个相邻的7替换为一个8）。游戏的目标是最大化最终序列中的最大数值。请帮助贝西获得尽可能高的分数！

输入格式

第一行输入包含NNN，接下来的NNN行给出游戏开始时序列的NNN个数字。

输出格式

请输出贝西能生成的最大整数。

输入输出样例 #1

输入 #1

4 1 1 1 2

输出 #1

说明/提示

在示例中，贝西首先合并第二个和第三个1，得到序列1 2 2，然后将两个2合并为3。注意，合并前两个1并不是最优策略。

暴力

拿到当前数组，先扫一遍，更新当前数组里的最大值；
从头到尾遍历，只要发现相邻两个数相等：
把这两个数合并成一个（数值 + 1），删掉后一个，生成新数组；
带着这个新数组，递归继续往下搜；
每条分支走到不能再合并为止，全部分支搜完，全局最大就是结果。

#include<bits/stdc++.h>usingnamespacestd;constintN=250;intn,ans;voidgo(vector<int>v){intbig=*max_element(v.begin(),v.end());ans=max(ans,big);for(inti=0;i<v.size()-1;i++){if(v[i]==v[i+1]){vector<int>z;for(intj=0;j<v.size();j++){if(i==j)z.push_back(v[j]+1);elseif(i+1==j)continue;elsez.push_back(v[j]);}go(z);}}}intmain(){//freopen("data.cpp","r",stdin);cin>>n;vector<int>v(n);for(inti=0;i<n;i++)cin>>v[i];go(v);cout<<ans;return0;}

无脑穷举所有合并顺序，重复计算多，指数级慢；
每遇到一对可合并的相邻数，就分出一条新递归分支；最坏情况（全是相同数）每步都有多个分叉，分支数量层层翻倍，是O(2ⁿ) 指数级。

区间动态规划

状态：dp[l][r]，数组中第 l 到 r 这一段区间，如果能完整合并成一个数，就存这个值；不能合并就存0。
按区间长度从小到大枚举；
对每个区间 [l, r]，中间随便切一刀分成左右两段 [l,x] 和 [x+1,r]；能合就合，左边值 + 1，存入 dp[l][r]，同时更新全局最大值 ans。

#include<bits/stdc++.h>usingnamespacestd;constintN=300;intn,// 数组长度v[N],// 存储原始输入的数字数组dp[N][N],// 区间 [l, r] 完全合并成 一个数 的值，等于0说明该区间无法合并成一个数ans;// 全局能合并出的最大数字intmain(){cin>>n;for(inti=1;i<=n;i++){cin>>v[i];dp[i][i]=v[i];// 单个数字本身就是一个数，无法再合并ans=max(ans,dp[i][i]);//原始数组的最大值}// 区间 DP 核心：按区间长度从小到大枚举（短区间→长区间）// 因为长区间的合并依赖于内部短区间的合并结果for(intlen=2;len<=n;len++)// 已知len=1时的最大值，从2开始for(intl=1;l+len-1<=n;l++){//左边界(l+len-1右边界)intr=l+len-1;// r：根据长度计算出的区间右边界dp[l][r]=0;//要么不能合并=0，否则就是下面的事for(intx=l;x<r;x++){//状态转移：枚举区间内的分割点 x，把 [l, r] 分成 [l, x] 和 [x+1, r]if(dp[l][x]!=0&&dp[l][x]==dp[x+1][r]){// 转移条件：相等dp[l][r]=dp[l][x]+1;//整个大区间可以合并成 【相等值 + 1】ans=max(ans,dp[l][r]);//更新全局答案}}}cout<<ans;return0;}