題干：

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.

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.

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

題目大意：

給n個珍珠，每個珍珠剛開始沒有顏色，每次操作可以任選連續(xù)的一段珍珠，然后涂上對應的顏色a[i]，一次操作的代價是這一段珍珠中的顏色種數(shù)的平方。求每個珍珠被都涂色的最小代價。n<=5e4。
例：1 3 3
答：2

解題報告：

考慮dp。首先想到n^2的dp。然后考慮優(yōu)化。因為每增加一個數(shù)字種類數(shù)，就要增加平方倍，所以種類數(shù)最多就是sqrt(1e5)這么多種類，再往前掃種類就沒有意義了，因為還不如直接一個一個涂色。又因為從當前點 i? 開始往前掃，數(shù)字種類數(shù)肯定是單調(diào)不減的，所以可以以每一個“顏色種類數(shù)”分塊，這樣有兩個好處：一是優(yōu)化了dp的搜索范圍，二是塊中的點一定是連續(xù)的（因為從后往前種類數(shù)單調(diào)不減），這也是為什么可以這樣維護的原因。

下面考慮維護這些塊：

方法1：先對每個數(shù)字都建一個塊，也就是剛開始是最初的雙向鏈表，發(fā)現(xiàn)當掃到第i個數(shù)字的時候，如果a[i]之前出現(xiàn)過，那么之前那個位置就沒有用了，可以直接刪除這個節(jié)點，合并對應的前驅(qū)和后繼即可。也就是說現(xiàn)在鏈表中的每個數(shù)字的位置代表的是對應塊的最后一個位置pos，代表的含義是先涂色到pos，然后pos+1一直到 i 用一次涂色。所以對應兩個細節(jié)：先更新dp值再cnt++；維護鏈表的時候這樣可以做到塊的代表元是當前塊的最后一個元素。換句話說，這樣跳表，每次跳到的pos是 這個數(shù)字a[pos] 在后綴中第一次出現(xiàn)的位置。賦初值dp[0]=0別忘了。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> #include<list> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int INF = 0x3f3f3f3f; const int MAX = 2e5 + 5; int n; int dp[MAX],a[MAX]; const int UP = 250; int pre[MAX],ne[MAX]; map<int,int> mp; int main() {while(~scanf("%d",&n)) {for(int i = 1; i<=n; i++) scanf("%d",a+i),pre[i] = i-1,ne[i] = i+1,dp[i] = INF;pre[0]=ne[n]=-1;mp.clear();for(int i = 1; i<=n; i++) {if(mp.find(a[i]) == mp.end()) mp[a[i]]=i;else {ne[pre[mp[a[i]]]] = ne[mp[a[i]]];pre[ne[mp[a[i]]]] = pre[mp[a[i]]];mp[a[i]]=i;}int cnt = 1;for(int j = pre[i]; ~j; j=pre[j]) {dp[i] = min(dp[i],dp[j] + cnt*cnt);cnt++;if(cnt > UP) break;}}printf("%d\n",dp[n]);}return 0 ; }

?

總結(jié)

以上是生活随笔為你收集整理的【HDU - 5009】Paint Pearls（dp，链表优化dp）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。