题解 P3146 【[USACO16OPEN]248】
览遍千秋
·
·
题解
前言
奇妙，最近在学区间动规，怎么区间动规的题目难度都那么高？
阶段、状态的划分
合并区间的长度为阶段，状态是每一个这样长度的区间。
状态的表示
---
## 本题的特殊性
当$opt[j][k]=opt[k+1][r]$的时候，才可以进行状态转移
---
## 状态转移方程
$$opt[j][r]=max(opt[j][r],opt[j][k]+1)$$
---
## 代码
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
#define maxn 257
int n,opt[maxn][maxn],a[maxn],ans;
inline void Init()
{
scanf("%d",&n);
for(register int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
opt[i][i]=a[i];
ans=max(a[i],ans);
}
}
inline void Work()
{
for(register int i=2;i<=n;i++)
{
for(register int j=1;j+i-1<=n;j++)
{
int r=i+j-1;
for(register int k=j;k<r;k++)
{
if(opt[j][k]==opt[k+1][r])
opt[j][r]=max(opt[j][r],opt[j][k]+1);
ans=max(ans,opt[j][r]);
}
}
}
printf("%d\n",ans);
}
int main()
{
Init();
Work();
return 0;
}
```