首页 > 代码库 > hdu 5009 Paint Pearls
hdu 5009 Paint Pearls
首先把具有相同颜色的点缩成一个点，即数据离散化。
然后使用dp[i]表示涂满前i个点的最小代价。对于第i+1个点，有两种情况：
1)自己单独涂，即dp[i+1] = dp[i] + 1
2)从第k个节点之后(不包括k)到第i+1个节点一次涂完，且一起涂的节点共有num种颜色，即dp[i+1] = dp[k] + num * num
从而可以得到状态转移方程dp[i+1] = min(dp[i], dp[k] + num * num)
但是如果从后往前遍历每一个k，会超时。
因此我们可以使用双向链表来把每种颜色最后出现的位置穿起来。对于每一个新加入的点，如果该点颜色没出现过，那么把它加入到双向链表的结尾。如果该点出现过，把它最后出现的位置从双向链表中删除，并把最新的位置加入到双向链表结尾。
需要注意的是要建立一个头节点，使得第一个节点不会因为后面出现了同样的颜色而被删除，从而无法计算从头到尾一次性涂完的情况。
第二个要注意的是如果num * num 已经大于了每个节点单独涂的代价 i，那么就没有必要再往前查找了。
代码如下：
1 #define MAXN 50005 2 #include <stdlib.h> 3 #include <iostream> 4 #include <stdio.h> 5 #include <map> 6 #include <limits.h> 7 8 using namespace std; 9 int arr[MAXN];//输入10 int l[MAXN];//记录前一个最后出现的颜色的位置11 int r[MAXN];//记录后一个最后出现颜色的位置12 int dp[MAXN];//dp[i]表示涂到第i个节点最小的代价13 int m;//离散化后数组的长度14 15 void solve()16 {17 map<int, int> exist;//map 存储出当前现过得颜色中，最后出现的位置18 int last = 1;//双向链表尾19 l[0] = -1;//头节点20 r[0] = 1;//头节点21 l[1] = 0;22 exist[arr[1]] = 1;23 dp[0] = 0;24 dp[1] = 1;25 26 for( int i = 2 ; i < m ; i++ )27 {28 if( exist.count(arr[i]) == 0 )29 {30 r[last] = i;//添加到尾部31 l[i] = last;32 last = i;33 exist[arr[i]] = i;34 }35 else36 {37 int tmp = exist[arr[i]];38 r[l[tmp]] = r[tmp];//删除tmp39 l[r[tmp]] = l[tmp];//删除tmp40 r[last] = i;41 l[i] = last;42 last = i;43 exist[arr[i]] = i;44 }45 46 int k = last;47 dp[i] = dp[i-1]+1;48 int num = 1;49 while( l[k] >= 0 )50 {51 dp[i] = min(dp[i], dp[l[k]] + num*num);52 num++;53 k = l[k];54 if( num * num > i )//剪枝55 {56 break;57 }58 }59 }60 printf("%d\n", dp[m-1]);61 }62 63 int main(int argc, char *argv[])64 {65 int n;66 while(scanf("%d", &n) != EOF)67 {68 int a;69 m = 1;70 for( int i = 1 ; i <= n ; i++ )//从1开始，位置0是头节点71 {72 scanf("%d", &a);73 if( i == 1 )74 {75 arr[m++] = a;76 }77 else if( arr[m-1] != a )//合并相同颜色的节点，离散化78 {79 arr[m++] = a;80 }81 }82 solve();83 }84 return 0;85 }
hdu 5009 Paint Pearls
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。