首页 > 代码库 > hdu5009 Paint Pearls （DP+模拟链表）
hdu5009 Paint Pearls （DP+模拟链表）
http://acm.hdu.edu.cn/showproblem.php?pid=5009
2014网络赛 西安 比较难的题
Paint PearlsTime Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 1951 Accepted Submission(s): 631 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 31 3 3103 4 2 4 4 2 4 3 2 2 Sample Output 27 Source 2014 ACM/ICPC Asia Regional Xi‘an Online Recommend hujie | We have carefully selected several similar problems for you: 5041 5040 5039 5038 5036 |
题意：
给出n个数，代表一排珍珠要涂的颜色，刚开始全都没有颜色。可以对连续若干个珍珠发动连涂，代价是这若干珍珠的不同颜色数的平方。涂完这串珍珠，求最小代价和。
题解：
nlog(n)的DP，还需要一些超碉方法来处理。
先进行一些小处理，最多5W珍珠，颜色其实也最多5W种，它给的颜色有10^9种，我先用map处理一下变成5w种。
然后连续若干个相同颜色的其实可以合并成一个。经过上面这两个处理，得到了新的珍珠数组。然后才是难点。
先看，最多5W个珍珠，233^2>50000，也就是233连涂就已经超过5W个分别单独涂的代价了。
动态规划，dp[i]表示涂完第i个珍珠所需的代价。
dp[i] = max( dp[i] , dp[k] + j*j)
j为j之后一直到i的不同颜色数。不同颜色数 j 最多为根号n，所以DP是O(n*根号n)的。
i从1到n，j从1到j*j>=i（因为1~i分别单独涂的代价是i）。
关键是如何求每个j对应的k。
假设已知对 i 的每个 j 对应的k，则我们可以求出对 i+1 的每个 j 对应的 k。比较容易想到。具体是这样：
设i的j对应的k为k(i,j)。
b[]为珍珠数组，
若b[i+1]为新出现的颜色，则
k( i+1 , j+1 ) = k( i , j )
k( i+1 , 1 ) = i + 1
若b[i+1]为以前就有的颜色，我们用一个last[]数组存每个颜色最后出现的位置，则
对 ( k( i , j ) > last[ b[i+1] ] ) 的j 有 k( i+1 , j+1 ) = k( i , j )
对 ( k( i , j ) < last[ b[i+1] ] ) 的j 则没有变化。
k( i+1 , 1 ) = i + 1
这样我们就能从i 推到 i+1了。
可以发现其中的操作都是连续一堆数向后移动一个下标，如果数组直接搞会TLE。我是用了模拟链表来搞，新颜色出现就直接在后面加，出现旧颜色就把那个分界点删掉，然后在后面加。
代码：
1 //#pragma comment(linker, "/STACK:102400000,102400000") 2 #include<cstdio> 3 #include<cmath> 4 #include<iostream> 5 #include<cstring> 6 #include<algorithm> 7 #include<cmath> 8 #include<map> 9 #include<set> 10 #include<stack> 11 #include<queue> 12 using namespace std; 13 #define ll long long 14 #define usll unsigned ll 15 #define mz(array) memset(array, 0, sizeof(array)) 16 #define minf(array) memset(array, 0x3f, sizeof(array)) 17 #define REP(i,n) for(i=0;i<(n);i++) 18 #define FOR(i,x,n) for(i=(x);i<=(n);i++) 19 #define RD(x) scanf("%d",&x) 20 #define RD2(x,y) scanf("%d%d",&x,&y) 21 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z) 22 #define WN(x) printf("%d\n",x); 23 #define RE freopen("xorin.txt","r",stdin) 24 #define WE freopen("xorin.txt","w",stdout) 25 #define mp make_pair 26 #define pb push_back 27 const int maxn=55555; 28 const int maxm=240; 29 int b[maxn],bn; 30 int cc[maxm+1]; 31 int dp[maxn]; 32 int d[maxn],dn,dq;///d[j]存着某个位置，存了dn个在1~dn，最后一个在dq; 33 int L[maxn],R[maxn];///L[d[dn]]存着第二个不同的的d[]的下标，再L一下是第三个的 34 int last[maxn];///last[x]表示x上次出现的位置的d[]的下标 35 int farm() { 36 int i,j,k; 37 // FOR(j,1,bn)printf("%3d",b[j]); 38 // puts(""); 39 mz(last); 40 L[0]=-1; 41 d[0]=0; 42 b[0]=0; 43 dn=1; 44 dq=1; 45 d[1]=1; 46 L[1]=0; 47 R[1]=0; 48 last[b[1]]=1; 49 FOR(i,1,bn) { 50 dp[i]=i; 51 j=1; 52 for(k=L[dq]; k!=-1; k=L[k]) { 53 if(cc[j]>=dp[i])break; 54 //printf("dp[%d]=min(%d , %d + %d)\n",i,dp[i], dp[d[k]],cc[j]); 55 dp[i]=min(dp[i] , dp[d[k]] + cc[j]); 56 j++; 57 } 58 if(last[b[i+1]]==0) { 59 dn++; 60 R[dq]=dn; 61 L[dn]=dq; 62 R[dn]=0; 63 dq=dn; 64 d[dn]=i+1; 65 66 } else { 67 j=last[b[i+1]]; 68 L[R[j]]=L[j]; 69 R[L[j]]=R[j]; 70 L[j]=dq; 71 R[j]=0; 72 R[dq]=j; 73 dq=j; 74 d[dq]=i+1; 75 } 76 last[b[i+1]]=dq; 77 } 78 return dp[bn]; 79 } 80 81 int a[maxn]; 82 map<int,int>S; 83 int main() { 84 int n,i,t; 85 int x; 86 FOR(i,0,maxm) { 87 cc[i]=i*i; 88 } 89 90 while(RD(n)!=EOF) { 91 S.clear(); 92 int cnt=0; 93 bn=0; 94 FOR(i,1,n) { 95 RD(x); 96 int t=S[x]; 97 if(t==0) S[x]=t=++cnt; 98 if(b[bn]!=t) b[++bn]=t; 99 }100 printf("%d\n",farm());101 }102 return 0;103 }
有点难，比赛时看了半天不懂，比完了搞了半天也不太懂……搞出来了以后发现思路应该还是挺简单的……
网上找到很多不同的方法，kuangbin菊苣说这个很水，他的并查集的方法我看不太懂……
hdu5009 Paint Pearls （DP+模拟链表）