题目
题目大意
给定一个1*n的地图，在里面玩2048，每次可以合并相邻两个（数值范围1-40），问最大能合出多少。注意合并后的数值并非加倍而是+1，例如2与2合并后的数值为3。
输入输出样例
输入样例#1：
4
1
1
1
2
输出样例#1：
3
题解
可以看出是区间$DP$
对于每一个区间记录的是能构成的最大值
因为是相邻的区间，思路是枚举每一个分界点
即$i$从$2$枚举到$n$
然后枚举$i$前的点$j$和$i$后的点$k$
就构成了两个相邻的区间$f_{j,i-1}$和$f_{i,k}$
$i-1$是因为是相邻的区间，所以$i$只能取一次
如果$f_{j,i-1}=f_{i,k}$，$f_{j,k}=max(f_{j,i-1}+1)$（注意不是$\times 2$，这是$248$不是$2048$）
然后试几组数据会发现答案不对，因为前面的区间可以被后面更新的区间更新
举个例子
$3\;2\;2\;1$
显然最优解是先合并两个$2$再用合出来的$3$与原来的$3$合并
为了解决这一问题，多次循环就好了
保证后面合出来的区间能与前面的区间合并
代码
# include<iostream>
# include<cstdio>
# include<cstring>
using namespace std;
int n;
int f[301][301];
void fre()
{
//freopen("248.in","r",stdin);
//freopen("248.out","w",stdout);
}
int main()
{
fre();
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&f[i][i]);
for(int l=1;l<=10;l++)
for(int i=2;i<=n;i++)
for(int j=i-1;j>=1;j--)
for(int k=i;k<=n;k++)
if(f[j][i-1]==f[i][k])
f[j][k]=max(f[j][k],f[j][i-1]+1);
int maxn=0;
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
maxn=max(maxn,f[i][j]);
printf("%d",maxn);
return 0;
}
