hdu 4362 Dragon Ball(dp + 优化) (2012 MultiUniversity Training Contest 7 )

http://acm.hdu.edu.cn/showproblem.php?pid=4362 

做这道题是 ，一眼看出来是 dp ，写了个 一般的dp 复杂度 m*n*n 直接 tle  好伤心。。。

想着怎么优化 ，但实在是不知道啊，后来看了 解题报告，明白了。。。。。

官方解题报告：

设dp[i][j]表示第i批龙珠中取第j个需要花费的最小体力。
dp[i][j] = min{ dp[i-1][k] + abs(pos[i-1][k]-pos[i][j]) } + cost[i][j];
如果枚举k的话总复杂度位m*n*n，会超时。
可以看出若每个状态只由上一层位置在其左边的状态的转移而来的话：  

dp[i][j] = min { dp[i-1][k] + pos[i][j] - pos[i-1][k] } + cost[i][j]
         = min { dp[i-1][k] - pos[i-1][k] } + pos[i][j] + cost[i][j]

dp[i][j] = min { dp[i-1][k] + pos[i-1][k] - pos[i][j] } + cost[i][j]
         = min { dp[i-1][k] + pos[i-1][k] } - pos[i][j] + cost[i][j]


dp[i-1][k]-pos[i-1][k]是个确定的值，就是相当于求位置在pos[i][j]左边的上一层状态中值最小的。由右边转移来的类似，再处理一遍右边转移来的取最优。
因为要对同一层的点排序，所以总复杂度是m*n*logn。

详情看代码：

 

  1 #include<stdio.h>
  2 #include<iostream>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<queue>
  7 #include<set>
  8 #include<map>
  9 #define Min(a,b)  a>b?b:a
 10 #define Max(a,b)  a>b?a:b
 11 #define CL(a,num)  memset(a,num,sizeof(a));
 12 #define inf 9999999
 13 #define maxn    1010
 14 #define mod 1000000007
 15 #define eps  1e-6
 16 #define ll  __int64
 17 using namespace std;
 18 int dp[60][maxn];
 19 struct node
 20 {
 21     int x;
 22     int val;
 23 }p[60][maxn] ;
 24 int q[maxn] ;
 25 int cmp(node a,node b)
 26 {
 27     return a.x < b.x ;
 28 }
 29 int cost(int i,int k,int j)
 30 {
 31     return dp[i - 1][k] + abs(p[i][j].x - p[ i-1][k].x)  + p[i][j].val;
 32 }
 33 int main()
 34 {
 35     int t,i,j,n,m,x;
 36     scanf("%d",&t);
 37     while(t--)
 38     {
 39         scanf("%d%d%d",&m,&n,&x);
 40 
 41         for( i =0 ; i <= m;++i)
 42           for(j = 0 ; j <= n;++j)
 43              dp[i][j] = inf;
 44         for(i = 1; i <= m ;++i)
 45         {
 46            for(j = 1 ; j <= n ;++j)
 47            {
 48             scanf("%d",&p[i][j].x);
 49            }
 50         }
 51 
 52         for(i = 1; i <= m ;++i)
 53         {
 54            for(j = 1 ; j <= n ;++j)
 55           {
 56             scanf("%d",&p[i][j].val);
 57           }
 58           sort(p[i] + 1,p[i] + 1 + n,cmp);//排序 后 比 第 j 个小的 肯定比第 j+1 小 ，为优化 打基础
 59         }
 60 
 61         for(i = 1; i <= n ;++i) dp[1][i] = abs(x - p[1][i].x) + p[1][i].val ;
 62         int head,tail,tmp,k;
 63         for( i =2; i <= m ;++i)
 64         {       head = 0;
 65                 tail = 0;
 66 
 67             for(k = j = 1; j <= n;++j)//pos[i][j]左边的上一层状态中值最小的
 68             {
 69 
 70                 while(k <= n &&p[i - 1][k].x <= p[i][j].x)
 71                 {
 72                     tmp =  cost(i,k,j);
 73                     while(tail > head && cost(i,q[tail - 1],j)>= tmp)  tail--;
 74                     q[tail++] = k;
 75                     k++;
 76                 }
 77                 if(tail > head)
 78                   dp[i][j] = cost(i,q[head],j);
 79 
 80             }
 81                 head = 0;
 82                 tail = 0;
 83 
 84              for(k = j = n ; j >= 1 ;--j)//pos[i][j]右边的上一层状态中值最小的
 85             {
 86 
 87                 while(k >= 1 &&p[i - 1][k].x >= p[i][j].x)
 88                 {
 89                     tmp =  cost(i,k,j);
 90                     while(tail > head && cost(i,q[tail - 1],j)>= tmp)  tail--;
 91                     q[tail++] = k;
 92                     k--;
 93                 }
 94 
 95                 if(tail > head)
 96                 {
 97                     tmp = cost(i,q[head],j);
 98                    if(tmp < dp[i][j]) dp[i][j] = tmp ;
 99                 }
100 
101 
102             }
103 
104 
105 
106         }
107         
108         int ans = dp[m][1] ;
109         for( i = 2; i <= n;++i)
110         {
111             if(ans > dp[m][i]) ans = dp[m][i] ;
112         }
113 
114         printf("%d\n",ans) ;
115 
116 
117 
118 
119     }
120 
121 }