https://www.luogu.org/problemnew/show/P3146
一道区间dp的题,以区间长度为阶段;
但由于要处理相邻的问题,就变得有点麻烦;
最开始想了一个我知道有漏洞的方程
if(f[i][k] != f[k + ][j]) f[i][j] = max(f[i][k],f[k + ][j]);
else f[i][j] = max(f[i][j],f[i][k] + );
可能f[i][k] = f[i][j],但他们可合并的并未相邻;
可以这样
#include <bits/stdc++.h>
#define read read()
#define up(i,l,r) for(int i = (l);i <=(r); i++)
using namespace std;
int read
{
int x = ; char ch = getchar();
while(ch < || ch > ) ch = getchar();
while(ch >= && ch <= ) {x = * x + ch - ; ch = getchar();}
return x;
}
const int N = ;
int n,a[N],f[N][N],ans;
int main()
{
freopen("248.in","r",stdin);
n = read;
up(i,,n) a[i] = read;
up(i,,n) {f[i][i] = a[i];ans = max(ans,f[i][i]);printf("[%d,%d] : %d\n",i,i,f[i][i]);}
up(L,,n)
up(i,,(n - L + ))
{
int j = i + L - ;
f[i][j] = ;
up(k,i,j - )
{
//if(f[i][k] != f[k + 1][j])
//f[i][j] = max(f[i][k],f[k + 1][j]);
//else
if(f[i][k] == f[k + ][j])
f[i][j] = max(f[i][j],f[i][k] + );
}
ans = max(f[i][j],ans);
//printf("[%d,%d] : %d\n",i,j,f[i][j]);
}
printf("%d",ans);
//printf("%d",f[1][n]);
return ;
}
区间长度由小到大,并且只合并相邻的,更新答案;
保证了能输出最大值;