首页 > 代码库 > HDOJ 5009 Paint Pearls
HDOJ 5009 Paint Pearls
DP + 优化 ,因为花费是n^2的,所以num×num 大于 DP【i】的时候就可以跳出了。。。。
Paint Pearls
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 1245 Accepted Submission(s): 395
Problem Description
Lee has a string of n pearls. In the beginning, all the pearls have no color. He plans to color the pearls to make it more fascinating. He drew his ideal pattern of the string on a paper and asks for your help.
In each operation, he selects some continuous pearls and all these pearls will be painted to their target colors. When he paints a string which has k different target colors, Lee will cost k2 points.
Now, Lee wants to cost as few as possible to get his ideal string. You should tell him the minimal cost.
In each operation, he selects some continuous pearls and all these pearls will be painted to their target colors. When he paints a string which has k different target colors, Lee will cost k2 points.
Now, Lee wants to cost as few as possible to get his ideal string. You should tell him the minimal cost.
Input
There are multiple test cases. Please process till EOF.
For each test case, the first line contains an integer n(1 ≤ n ≤ 5×104), indicating the number of pearls. The second line contains a1,a2,...,an (1 ≤ ai ≤ 109) indicating the target color of each pearl.
For each test case, the first line contains an integer n(1 ≤ n ≤ 5×104), indicating the number of pearls. The second line contains a1,a2,...,an (1 ≤ ai ≤ 109) indicating the target color of each pearl.
Output
For each test case, output the minimal cost in a line.
Sample Input
3 1 3 3 10 3 4 2 4 4 2 4 3 2 2
Sample Output
2 7
Source
2014 ACM/ICPC Asia Regional Xi‘an Online
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <map> using namespace std; int n,a[50050],b[50050],last[50050]; int dp[50050]; map<int,int> mp; int fa[50050]; int find(int x) { if(x==fa[x]) return x; return fa[x]=find(fa[x]); } void bing(int x,int y) { int X=find(x),Y=find(y); if(X==Y) return ; fa[Y]=X; } int main() { while(scanf("%d",&n)!=EOF) { for(int i=1;i<=n;i++) { scanf("%d",a+i); b[i]=a[i]; } sort(b+1,b+n+1); int cnt=unique(b,b+n+1)-b; for(int i=1;i<cnt;i++) { mp[b[i]]=i; } for(int i=0;i<=n;i++) { a[i]=mp[a[i]]; fa[i]=i; last[i]=-1; } for(int i=1;i<=n;i++) { if(last[a[i]]!=-1) { bing(last[a[i]]-1,last[a[i]]); } last[a[i]]=i; dp[i]=i; int num=0; for(int j=i;j>0;j=find(j-1)) { num++; if(num*num>dp[i]) break; int next=find(j-1); dp[i]=min(dp[i],dp[next]+num*num); } } printf("%d\n",dp[n]); } return 0; }
HDOJ 5009 Paint Pearls
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。