hdu 5009 Paint Pearls-白红宇

hdu 5009 Paint Pearls

阅读量：6601 次

发布时间：2019-06-24

本文共 1906 字，大约阅读时间需要 6 分钟。

首先把具有相同颜色的点缩成一个点，即数据离散化。

然后使用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 
     
       3 #include 
      
        4 #include 
       
         5 #include 
         6 #include 
         
           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
          
            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 }

转载于:https://www.cnblogs.com/jostree/p/3995813.html

你可能感兴趣的文章