HDU4362Dragon Ball【dp优化】

【比赛提醒】BestCoder 你报名了吗？（点击报名） 
【科普】什么是BestCoder？如何参加？

Dragon Ball

Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2196    Accepted Submission(s): 767

Problem Description

Sean has got a Treasure map which shows when and where the dragon balls will appear. some dragon balls will appear in a line at the same time for each period.Since the time you got one of them,the other dragon ball will disappear so he can only and must get one Dragon ball in each period.Digging out one ball he will lose some energy.Sean will lose |x-y| energy when he move from x to y.Suppose Sean has enough time to get any drogan ball he want in each period.We want to know the minimum energy sean will lose to get all period’s dragon ball.

 

Input

In the first line a number T indicate the number of test cases.Then for each case the first line contain 3 numbers m,n,x(1<=m<=50,1<=n<=1000),indicate m period Dragon ball will appear,n dragon balls for every period, x is the initial location of sean.Then two m*n matrix. For the first matrix,the number in I row and J column indicate the location of J-th Dragon ball in I th period.For the second matrix the number in I row and J column indicate the energy sean will lose for J-th Dragon ball in I-th period.

 

Output

For each case print a number means the minimum energy sean will lose.

 

Sample Input

1 3 2 5 2 3 4 1 1 3 1 1 1 3 4 2

 

Sample Output

8

 

Author

FZU

 

Source

2012 Multi-University Training Contest 7

这个题卡死我了啊啊啊啊啊啊啊啊啊

终于找到错了啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊

啊啊啊啊啊啊啊啊

大意:有n个periodm个龙珠

每个period会出现一些龙珠

但是你每个period只能收集一个龙珠

告诉你每个龙珠在每个时期出现的位置和digging的cost

问最少花费多少cost

分析：

刚开始读错题意了  题目描述？额出问题了？我以为每个水晶球去过之后就不能去了呢

又是1000状态压缩都没法压

之后看到正确题意之后第一反应出来一个10^7的算法

交了一次TLE

之后我就想怎么优化 

看别人题意的时候看到他说用单调队列优化

我想了大概十分钟才终于想通了

对于一个位置pos

dp[i][j] = min(dp[i - 1][k] + abs（pos - k) + cost[i][j])

将其展开

对于pos之前的额k

dp[i][j] = min(dp[i - 1][k] + pos - k + cost[i][j])

对于之后的k

dp[i][j] = min(dp[i - 1][k] + k - pos+ cost[i][j])

我的思路是把每个period的位置都排一次序

对于dp[i][j]只要正着扫一遍k用一个单调队列

然后在倒着扫一遍

然后就wa啊  

后来才找到wa点

我们每次往单调队列里push的不能跟当前状态有任何关系==

以为他会影响到后续状态==

只要把dp方程改一下

pos之前的k dp[i][j] = min(dp[i - 1][k] - pos[i - 1][k]) + pos[i][j] + cost[i][j]

pos之后的k dp[i][j] = min(dp[i - 1][j] + pos[i - 1][k]) + cost[i][j] - pos[i][j]

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

const int maxn = 55;
const int maxm = 1005;
const int INF = 1000000000;

struct Node {
    int x, y, pos;
}node[maxn][maxm];
bool cmp(Node n1, Node n2) {
    return n1.pos < n2.pos;
}
int cost[maxn][maxm];
int dp[maxn][maxm];
priority_queue<int, vector<int>, greater<int> > q1, q2;

int main() {
    int t, n, m, x;
    scanf("%d",&t);
    while(t--) {
        scanf("%d %d %d",&n, &m, &x);
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                scanf("%d",&node[i][j].pos);
                node[i][j].x = i; node[i][j].y = j;
            }
        }
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                scanf("%d",&cost[i][j]);
            }
        }
        for(int i = 1; i <= n; i++) {
            sort(node[i] + 1, node[i] + 1 + m, cmp);
        }
        memset(dp, 0x3f, sizeof(dp));
        for(int j = 1; j <= m; j++) {
            dp[1][j] = abs(x - node[1][j].pos) + cost[node[1][j].x][node[1][j].y];
        }
        for(int i = 2; i <= n; i++) {
            int k = 1;
            while(!q1.empty()) q1.pop();
            while(!q2.empty()) q2.pop();
            for(int j = 1; j <= m; j++) {
                for(k; k <= m; k++) {
                    if(node[i - 1][k].pos > node[i][j].pos) {
                        break;
                    }
                    q1.push(dp[i - 1][k] - node[i - 1][k].pos);
                }
                if(!q1.empty()) {
                    dp[i][j] = min(dp[i][j], q1.top() + node[i][j].pos + cost[node[i][j].x][node[i][j].y]);
                }
            }
            k = m;
            for(int j = m; j >= 1; j--) {
                for(k; k >= 1; k--) {
                    if(node[i - 1][k].pos < node[i][j].pos) break;
                    q2.push(dp[i - 1][k] + node[i - 1][k].pos);
                }
                if(!q2.empty()) {
                    dp[i][j] = min(dp[i][j], q2.top() + (- node[i][j].pos + cost[node[i][j].x][node[i][j].y]));
                }
            }
        }
        int ans = INF;

        for(int j = 1; j <= m; j++) {
            ans = min(ans, dp[n][j]);
        }
        printf("%d
", ans);
    }
    return 0;
}