Paint Pearls
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 2 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 k 2 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 4), indicating the number of pearls. The second line contains a 1,a 2,...,a n (1 ≤ a i ≤ 10 9) indicating the target color of each pearl.
For each test case, the first line contains an integer n(1 ≤ n ≤ 5×10 4), indicating the number of pearls. The second line contains a 1,a 2,...,a n (1 ≤ a i ≤ 10 9) 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
Recommend
hujie
题目大意：
给定一系列的颜色。能够划分为随意多个随意大小的区间。每一个区间的花费为 区间颜色数的平方，问你总花费最小是多少？
解题思路：
用动态规划，双向链表事实上就是维护前面不同的元素，同样的元素删除。
我參照的是：http://blog.csdn.net/u011345136/article/details/39759935
解题代码：
#include <iostream>
#include <map>
#include <cstdio>
using namespace std;
const int maxn=51000;
int n,d[maxn],dp[maxn],pre[maxn],next[maxn];
map <int,int> mp;
//mp 记录数字相应的下标
//pre 记录前驱
//next 记录后继
void solve(){
mp.clear();
for(int i=1;i<=n;i++){
pre[i]=i-1;
next[i]=i+1;
dp[i]=(1<<30);
}
dp[0]=0;pre[0]=-1;
for(int i=1;i<=n;i++){
if(mp.find(d[i])==mp.end()) mp[d[i]]=i;
else{
int id=mp[d[i]];
next[pre[id]]=next[id];
pre[next[id]]=pre[id];
mp[d[i]]=i;
}
int c=0;
for(int j=pre[i];j!=-1;j=pre[j]){
c++;
dp[i]=min(dp[i],dp[j]+c*c);
if(c*c>=i) break;
}
}
printf("%d\n",dp[n]);
}
int main(){
while(scanf("%d",&n)!=EOF){
for(int i=1;i<=n;i++) scanf("%d",&d[i]);
solve();
}
return 0;
}
本文转自mfrbuaa博客园博客，原文链接：http://www.cnblogs.com/mfrbuaa/p/5095919.html，如需转载请自行联系原作者
