题解 P3146 【[USACO16OPEN]248 G】
题解 P3146 【[USACO16OPEN]248 G】
详细的讲一下该题。
一、题意
一个数组，两个相同的相邻数字可以组合成一个比这两个数字原来+1的数。就像下面这个数组的组合操作：
1 1 2 3
|
\_/2 2 3 --->把第一、第二个元素合并
要你求出该数组可以组合成的最大数字。
举个例子：
4
2 2 2 2（下面是最优值组合过程）
|
\_/3 2 2
|
\_/3 3
|
\_/
4 --->最优值二、初步找算法。
对于每一个组合起来的数，我们都可以把它看做是由一堆初始数字组合而成，自然而然就想到了区间DP。
三、明确解题具体方法
-
定义f [ i ] [ j ]，表示在 i 到 j 的范围内组合成的最大的数。
-
那么当前范围的最大值就有可能是当前区间分成地任意两个小区间的最大值组合而成（两个小区间组合之数的最大值相等才行）。
-
根据上述，我们可以推断出DP的方法：
把当前区间任意划分成两个小区间，再依次找出最优组合方案，将该方案存入当前区间，并更新最大值。
-
总结出DP式核心程序：
for(int k=i;k<j;k++)//枚举两个小区间的分界点
if(f[i][k]==f[k+1][j])//如果小区间最大值相同
f[i][j]=max(f[i][j],f[i][k]+1);//更新当前区间
ans=max(ans,f[i][j]);//存最大值四、完善细节
-
初始化：在读入每个元素时，将f数组的当前位置到当前位置（f [ i ] [ i ]）设为元素值。
-
最大值在刚开始读入时就要开始更新（以免后面没得组合的情况）
五、思考争议
有人会问：如果两个小区间的最大值不一样，导致无法组合，甚至丧失最后的最优值，怎么办？
当初我也想过这个问题，没有过多的去思考，用了三维，是避免了所谓上面的问题，但是很可惜，炸时间。
那为什么还可以这样做呢？因为题目说，合并之后的数的最大值是原来的数的值+1，那比起你用非最大值合并，还不如直接取当前还没合并的最大值？
如果还没弄明白，那你可以找一些数据来摆弄摆弄就懂了。
六、完整代码
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
using namespace std;
int n,a[248+5],f[248+5][248+5],j,ans=-1;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
f[i][i]=a[i];
ans=max(ans,a[i]);
}
for(int l=2;l<=n;l++)
for(int i=1;i<=n-l+1;i++)
{
j=i+l-1;
for(int k=i;k<j;k++)
if(f[i][k]==f[k+1][j])f[i][j]=max(f[i][j],f[i][k]+1);
ans=max(ans,f[i][j]);
}
cout<<ans;
return 0;
}
//代码那么简单还抄？七、FOR管理员：
这篇题解思路可能有重复，但解题的步骤绝对是该题题解中最详细清晰的，管理员过一下，谢谢。