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 k ² 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×10 ⁴), indicating the number of pearls. The second line contains a ₁,a ₂,...,a _n (1 ≤ a _i ≤ 10 ⁹) 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 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
       using namespace std; int n,a[50050],b[50050],last[50050]; int dp[50050]; map
       
         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
        
         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; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：HDU5012 Dice 记忆化搜索	下一篇：hdu 5015 233 Matrix

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: