Ural 2072：Kirill the Gardener 3（DP）

http://acm.timus.ru/problem.aspx?space=1&num=2072

题意：有n朵花，每朵花有一个饥渴值。现在浇花，优先浇饥渴值小的（即从小到大浇），浇花需要耗费1个单位时间，从第i个位置走到第j个位置需要耗费abs（j-i）个单位时间，问浇完所有的花需要耗费的最少时间是多少。

思路：考虑到有饥渴值一样的花，那么只要考虑怎么在饥渴值相同的情况下取最优，那问题便可以迎刃而解了。

首先想，要让时间耗费的少，那么就尽量不要走重复的路程，所以想到这里，可以确定：对于某一个饥渴值x，一定是从饥渴值为x的最左边的位置走到饥渴值为x的最右边的位置，或者从最右边的位置走到最左边。因为这样就可以变成一条直线了，不会走多余的路程。

考虑到我们只需要知道每个饥渴值对应的最左边和最右边的位置，因此我们只要处理出Left[i]，Right[i]数组即可。因为数据大，所以需要离散化。

定义两个状态：dp[i][0]为走到饥渴值为i的花的时候从最左边走到最右边耗费的最短时间，dp[i][1]为走到饥渴值为i的花的时候从最右边走到最左边耗费的最短时间。

知道这两个状态后，转移方程就不难列出：

dp[i][0] = Right[i] - Left[i] + min(dp[i-1][1] + abs(Left[i-1] - Left[i]), dp[i-1][0] + abs(Right[i-1] - Left[i]));

dp[i][1] = Right[i] - Left[i] + min(dp[i-1][1] + abs(Left[i-1] - Right[i]), dp[i-1][0] + abs(Right[i-1] - Right[i]));

注意要用longlong。可怜的队友因为这个抓狂了一个下午。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define N 100005
#define INF 0x3f3f3f3f
LL dp[N][2], a[N], b[N]; int Left[N], Right[N];
// dp[i][0] Left -> Right , dp[i][1] Right -> Left

int main() {
    int n;
    while(~scanf("%d", &n)) {
        for(int i = 1; i <= n; i++) scanf("%lld", &a[i]), b[i] = a[i];
        sort(b + 1, b + 1 + n);
        int cnt = unique(b + 1, b + 1 + n) - b - 1;
        memset(Left, INF, sizeof(Left));
        for(int i = 1; i <= n; i++) { // 离散化
            a[i] = lower_bound(b + 1, b + 1 + cnt, a[i]) - b;
            Left[a[i]] = min(Left[a[i]], i);
            Right[a[i]] = max(Right[a[i]], i);
        }
        dp[1][0] = Right[1] - 1; // 走到右端
        dp[1][1] = Right[1] - Left[1] + Right[1] - 1; // 先到右端再走到左端
        for(int i = 2; i <= cnt; i++) {
            int dis = Right[i] - Left[i];
            dp[i][0] = min(dp[i-1][1] + abs(Left[i-1] - Left[i]), dp[i-1][0] + abs(Right[i-1] - Left[i])) + dis;
            dp[i][1] = min(dp[i-1][1] + abs(Left[i-1] - Right[i]), dp[i-1][0] + abs(Right[i-1] - Right[i])) + dis;
        }
        printf("%lld
", min(dp[cnt][0], dp[cnt][1]) + n);
    }
    return 0;
}