hdu 4412 Sky Soldiers(区间DP)-白红宇

hdu 4412 Sky Soldiers(区间DP)

阅读量：4128 次

发布时间：2019-05-25

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

题目问题抽象之后为：在一个x坐标轴上有N个点，每个点上有一个概率值，可以修M个工作站，

求怎样安排这M个工作站的位置，使得这N个点都走到工作站的距离期望值最小？

解题报告人：SpringWater(GHQ)

解题思路：状态方程：dp[i][j] = min{ dp[i - 1][k - 1] + cost[k][j] }dp[i][j]表示在1到j修i个站，的最小期望值，

cost【k】【j】是我预处理的k到j这段区间修一个工作站的期望值，因为在求cost【k】【j】具

有单调性，所以可以在O（n^2）复杂度算出

代码如下：

#include
   
    #include
    
     #include
     #include
      
       #include
       
        #include
        
         #define MAXN 1005using namespace std;double dp[55][MAXN], cost[MAXN][MAXN];map
         
           hash;struct Info{double pos;double p;}info[MAXN];int main(){ int N, M, i, n, a, j, k, pos; double l, r, suml, sumr; double b, min, temp, t; while(scanf("%d%d",&N, &M)&&(N + M)) { hash.clear(); for( i = 1; i <= N; ++ i ) { scanf("%d", &n);++n; while(--n) { scanf("%d%lf", &a, &b); hash[a]+=b; } } N = 0; for(map
          
           ::iterator it = hash.begin(); it != hash.end(); ++it) { info[++N].pos = it->first; info[N].p = it->second; } for(j = N; j >= 1; j--) { pos = j; cost[j][j] = 0; l = r = suml = 0; sumr = info[j].p; for(k = j-1; k >= 1; --k ) { suml += info[k].p; l += (info[pos].pos-info[k].pos) * info[k].p; temp = l + r; while((pos > 1)&&(temp>(t = (l + r + (sumr - suml) * (info[pos].pos - info[pos - 1].pos))))) { l -= suml * (info[pos].pos - info[pos - 1].pos); r += sumr * (info[pos].pos - info[pos - 1].pos); --pos; suml -= info[pos].p; sumr +=info[pos].p; temp = t; } cost[k][j] = temp; } } for(i = 1; i <= N; i++)dp[0][i] = 1e300; for(i = 0; i <= M; i++)dp[i][0] = 0; for(i = 1; i <= M; i++) { for(j = N; j >= 1; j--) { min = dp[i-1][j-1] + cost[j][j]; for(k = j-1; k >= 1; --k ) { if(dp[i - 1][k - 1] + cost[k][j] < min)min = dp[i - 1][k - 1] + cost[k][j]; } dp[i][j] = min; } } printf("%0.2lf\n",dp[M][N]); } return 0;}