HDU5009 DP。需要简单优化下就可以了。

Paint Pearls

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 715 Accepted Submission(s): 228

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.

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.

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

注意到 n <= 5*10^4 而且花费是 k^2 所以DP转移的时候， 转移不同的不要超过 sqrt(i)个。   为了找到不同的，可以搞个set去转移。   也可以搞个并查集去合并。

/* ***
Author :kuangbin
Created Time :2014/9/14 23:23:59
File Name :E:\2014ACM\2014网络赛\2014西安\HDU5009.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;
const int MAXN = 50010;
int a[MAXN];
int F[MAXN];
int find(int x){
if(F[x] == -1)return x;
return F[x] = find(F[x]);
}
void bing(int x,int y){
int t1 = find(x), t2 = find(y);
if(t1 != t2)F[t2] = t1;
}
int b[MAXN];
int last[MAXN];
int dp[MAXN];

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int n;
while(scanf(“%d”,&n) == 1){
int cnt = 0;
for(int i = 1;i <= n;i++){
scanf(“%d”,&a[i]);
b[cnt++] = a[i];
}
sort(b,b+cnt);
cnt = unique(b,b+cnt) - b;
map<int,int>mp;
for(int i = 0;i < cnt;i++){
mp[b[i]] = i;
last[i] = -1;
}
for(int i = 1;i <= n;i++)a[i] = mp[a[i]];
dp[0] = 0;
F[0] = -1;
for(int i = 1;i <= n;i++){
F[i] = -1;
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(numnum >= dp[i])break;
int nxt = find(j-1);
dp[i] = min(dp[i],dp[nxt]+numnum);
}
}
printf(“%d\n”,dp[n]);
}
return 0;
}