4458: 【基础】相同数的合并(2213)
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
给定一个 的地图，在里面合并数字，每次可以合并相邻两个相同的数（数值范围 ），问序列中出现的最大数字的值是多少。
注意合并后的数值并非加倍而是，例如 与 合并后的数值为 。
输入
第 行有一个整数 ()。
接下来 行，每行有 个整数。
输出
输出一个整数，代表能得到的最大的整数。
样例输入 复制
4
1
1
1
2样例输出 复制
3提示
样例解释
在此示例中，首先合并第二个 和第三个 以获得序列 ，然后将 合并为 。
请注意，合并前两个 不是最佳选择。
#include<bits/stdc++.h>
using namespace std;
/*
求:序列中出现的最大数字的值是多少
合并条件：f[L,K]== f[K+1][R]
f[L,R]= max(f[L,R],f[L,K]+1)
边界条件：f[i][j]= -∞
f[i][i]= a[i] 自己这个数合并得到的结果就是自己
*/
const int N=260;
int a[N],f[N][N];
int n,ans =0; //ans表示最大数
int main(){
cin>>n; //初始化
memset(f,-0x3f,sizeof(f));
for(int i= 1;i<= n;i++){
cin>>a[i];
f[i][i] = a[i];
ans=max(ans,a[i]);
}
//枚举可能的长度
for(int len =2;len<= n;len++){
//枚举所有区间可能的起点
for(int i=1;i+len-1<= n;i++){
int j=i+len-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(f[i][j],ans);
}
}
}
}
cout<<ans;
return 0;
}