【BZOJ 4580】【Usaco2016 Open】248

http://www.lydsy.com/JudgeOnline/problem.php?id=4580

区间dp，f(i,j)表示区间[i,j]全部合成一个数，这个数是多少。

可以归纳证明[i,j]如果可以合成一个数，那么只能合成这一个数

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;const int N = 253;int n, a[N], f[N][N];int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", a + i);
for (int i = 1; i <= n; ++i)
f[i][i] = a[i];for (int i = n - 1; i >= 1; --i)
for (int j = i + 1; j <= n; ++j)
for (int k = i; k < j; ++k)
if (f[i][k] && f[k + 1][j] && f[i][k] == f[k + 1][j]) {
f[i][j] = f[i][k] + 1;
break;
}int ans = 0;
for (int i = n; i >= 1; --i)
for (int j = i; j <= n; ++j)
ans = max(ans, f[i][j]);printf("%d\n", ans);
return 0;
}