Educational Codeforces Round 83 (Rated for Div. 2) E.Array Shrinking(区间dp/合并问题+分段问题)

题目

n(n<=500)个数，第i个数为ai(1<=ai<=1e3)，

每次你可以选择两个相邻的且相等(不妨值为v)的数，将这两个数替换为一个v+1的数，后面的数会跟上来

问以这样的方式合并，a[]数组最后最少能剩几个数

思路来源

https://www.cnblogs.com/zxytxdy/p/12454472.html

题解

学了区间dp之后，感觉这个题好sb啊，可惜当时不会orz

两种做法，

第一种，前一半是合并的区间dp，dp[l][r]维护这一段能合成一段的最大值，

只要能合并成一段，就加一个seg[l,r]，代价为1，最后用所有seg来为最终的结果做分段的区间dp

第二种，dp[l][r]仍维护这一段能合成一段的最大值，ans[l][r]代表这一段最少剩几个，

如果能合成一段，ans[l][r]显然为1，否则ans[l][r]=min(ans[l][r],ans[l][k]+ans[k+1][r])(l<=k<r)

代码

#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,m,dp[N][N],a[N],f[N];
struct seg{
	int l,r;
}e[N*N];
bool operator<(seg a,seg b){
	return a.r<b.r;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		dp[i][i]=a[i];		
	}
	for(int len=2;len<=n;++len){
		for(int l=1;l+len-1<=n;++l){
			int r=l+len-1;
			dp[l][r]=-1;
			for(int k=l;k<r;++k){
				if(~dp[l][k] && dp[l][k]==dp[k+1][r]){
					dp[l][r]=dp[l][k]+1;
//					printf("[%d,%d]\n",l,r);
					e[++m]=(seg){l,r};
					break;
				}
			}
		}
	}
	sort(e+1,e+m+1);
	int now=1;
	for(int i=1;i<=n;++i){
		f[i]=f[i-1]+1;//f[i]<=i 从前面的段多加一个 
		while(now<=m && e[now].r==i){
			f[i]=min(f[i],f[e[now].l-1]+1);
			now++;
		}
	}
	printf("%d\n",f[n]);
	return 0;
}