1312E Array Shrinking

1312E Array Shrinking
题意：
给你 $n(1\le n\le 500)$n(1≤n≤500) 长的数组，你可以任意次操作使得满足 $a\left[n\right]=a[n+1]$a[n]=a[n+1] 的两个数被替换为 $a\left[n\right]+1$a[n]+1 ，求数组最小长为多少。
思路：
区间 $dp$dp
观察 $n$n 的范围，可知这道题可以采用 $O\left(n^3\right)$O(n3) 的算法来解决。
先用区间 $dp$dp 预处理，再 $dp$dp 取最小值。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;

ll n,a[1005],num[1005][1005],f[1005];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		num[i][i]=a[i];//初始化num[i][i]为本身
	}
	for(int len=1;len<=n;len++){//枚举区间长度
		for(int l=1;l+len<=n;l++){//枚举l端点
			int r=l+len;//r端点
			for(int k=l;k<r;k++){
				if(num[l][k]==num[k+1][r] && num[l][k]>0)//将一个区间切为两部分 如果这两部分相等 合并区间
					num[l][r]=num[l][k]+1;
			}

		}
	}
	for(int i=1;i<=n;i++){
		f[i]=f[i-1]+1;
		for(int j=1;j<=i;j++){
			if(num[j][i]>0)
				f[i]=min(f[i],f[j-1]+1);
		}
	}
	cout<<f[n];
	return 0;
}