[HDU 5009]Paint Pearls(DP)

[HDU 5009]Paint Pearls(DP)

题面

一个序列，每个值代表一种颜色，每次选一个区间覆盖，覆盖的代价是区间内颜色种类数的平方，直到覆盖整个数列，求最小花费

分析

设(dp[i])表示覆盖前(i)位的最小花费，那么显然有

[dp[i]=min_{j=0}^{i-1}(dp[j]+num(j+1,i)^2) ]

其中(num(l,r))表示区间([l,r])内的颜色种类数。

直接求解显然是(O(n^2))的，而这个式子看起来也很难优化。考虑剪枝。

首先(dp[i] leq i), 因为如果每个点单独覆盖,每次覆盖的代价是1,总代价为i

还有一个强力的剪枝是重复的数只用保留最后一个，其他重复的可以删去。考虑到j从i-1倒序枚举到1时，若出现重复的a[j]，加入之后不会使num变大.如果j是最后一个,那么前面的数的代价已经在计算dp[j]的时候算过了.因此不会影响结果

这样就可以保证转移时每个权值只出现一次.又因为权值总数的平方超过(i)时就可以停止转移。总时间复杂度为(O(nsqrt n)).删除操作可以用双向链表实现

代码

//http://119.29.55.79/problem/1502
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 100000
using namespace std;
int n;
int a[maxn+5];
void discrete(int *a,int n) {
	static int b[maxn+5];
	for(int i=1; i<=n; i++) b[i]=a[i];
	sort(b+1,b+1+n);
	int sz=unique(b+1,b+1+n)-b-1;
	for(int i=1; i<=n; i++) a[i]=lower_bound(b+1,b+1+sz,a[i])-b;

}

struct list {
	int pre[maxn+5],nex[maxn+5];
	void ini(int n) {
		pre[0]=-1;//相当于NULL
		for(int i=1; i<=n; i++) {
			pre[i]=i-1;
			nex[i]=i+1;
		}
	}
	void del(int x) {
		nex[pre[x]]=nex[x];
		pre[nex[x]]=pre[x];
	}
} L;
int lst[maxn+5];
int dp[maxn+5];
void ini(){
	memset(lst,0,sizeof(lst));
	memset(dp,0,sizeof(dp));
}
int main() {
	while(scanf("%d",&n)!=EOF) {
		ini(); 
		for(int i=1; i<=n; i++) scanf("%d",&a[i]);
		discrete(a,n);
		L.ini(n);
		dp[0]=0;
		for(int i=1; i<=n; i++) dp[i]=i; //每个数一段,答案最大不超过i
		for(int i=1; i<=n; i++) {
			if(lst[a[i]]) L.del(lst[a[i]]);	//相同的数只保留最后一个
			//考虑到j从i-1倒序枚举到1时，若出现重复的a[i]，除第一次出现外应该删去，
			//因为枚举到的a[i]加入num^2部分不会使num变大,所以dp[i]和它前后的dp值应该是等价的
			lst[a[i]]=i;
			int num=0;
			for(int j=L.pre[i]; j!=-1; j=L.pre[j]) {
				num++;
				if(num*num>i) break;//如果超过i显然不优，可以直接break掉
				dp[i]=min(dp[i],dp[j]+num*num);
			}
		}
		printf("%d
",dp[n]);
	}
}