首页 > 代码库 > hdu 5009 Paint Pearls (DP)
hdu 5009 Paint Pearls (DP)
从前往后DP；
先离散化；
假设DP到第i个位置。
las[i]表示第i种颜色最后一次出现的位置。
t[k]表示满足w(t[i],i)==k的最小下标，w(a,b)表示从a,a+1,a+2......b这段区间的不同颜色的数量是多少。
然后每次先更新t数组，再更新dp数组，k只需从1枚举到sqrt(n)，所以复杂度为（n*sqrt(n)）.
数组更新的时候，有两种情况。
1.第i个位置的颜色前边没出现过，则全部t[i]都要更新，表示为 for(int j=up;j>=1;j--)t[j+1]=t[j]，t[1]=i,up++;
2.第i个位置的颜色前边出现过，则需更新部分t[i]，只需更新t[i]>las[a[i]]的那些t[i].
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <map>#define inf 0x3f3f3f3fusing namespace std;const int maxn=50005;map<int,int>mp;int cnt,n;int las[maxn],dp[maxn],a[maxn],t[250];//las[i]表示最后一次i出现的位置，dp[i]表示到前i个的最小花费。int ID(int x){ if(!mp.count(x))mp[x]=++cnt; return mp[x];}void run(){ mp.clear(); cnt=0; for(int i=1;i<=n;i++){ scanf("%d",a+i); a[i]=ID(a[i]); } memset(las,0,sizeof las); int up=1; t[1]=1; dp[1]=1; las[a[1]]=1; for(int i=2;i<=n;i++){ dp[i]=inf; if(!las[a[i]]){ for(int j=up;j>=1;j--)t[j+1]=t[j]; if(up*up<=n)up++; t[1]=i; } else { int m=up; while(m&&t[m]<=las[a[i]])m--; for(int j=m-1;j>=1;j--)t[j+1]=t[j]; if(m)t[1]=i; } las[a[i]]=i; for(int j=1;j*j<=i;j++){ dp[i]=min(dp[i],dp[t[j]-1]+j*j); } } printf("%d\n",dp[n]);}int main(){// freopen("in","r",stdin); while(scanf("%d",&n)>0)run(); return 0;}
hdu 5009 Paint Pearls (DP)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。