URAL 2072 Kirill the Gardener 3

PRoblem

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

题意

一行 n 朵花，每朵有个饥渴系数，园丁要按饥渴系数升序地浇完所有花，他一开始站在最左边那朵花那里。

每朵花要浇 1 个时间，从位置 i 走到位置 j 要花 abs( i - j ) 个时间，问按要求浇完所有花的最短时间。

Analysis

对每一个饥渴系数的那些花，肯定是从最左边的一朵向右一路淋到最右边一朵，然后停在最右边那朵那里；或者反过来，从右到左，然后停在最左边那朵。

因为最左和最右都要淋，所以一定要走一次从最左到最右这段路程。而如果最终停在中间的某朵的话，肯定有一段路是没必要走却重复走了的。

如果要从这个系数的最左边一朵出发，那可能是从上一个系数的最左边或最右边一朵走过来的。

定义状态：dp [i][0]：饥渴系数为 i 时，从右到左地淋花然后停在最左边那朵所走的最短路程

dp [i][1]：…，从左到右…停在最右边…

left [i]：饥渴系数为 i 的花中最左边那朵的位置

right [i]：…最右边…

状态转移：dp[i][0] = right[i] - left[i] + min { dp[i-1][0] + abs( left[i-1] - right[i] ) , dp[i-1][1] + abs( right[i-1] - right[i] ) }

dp[i][1] = right[i] - left[i] + min { dp[i-1][0] + abs( left[i-1] - left[i] ) , dp[i-1][1] + abs( right[i-1] - left[i] ) }

饥渴系数范围太大，需要对其离散化。

实测数据会爆 int，要用 long long。

Source code

#include <cstdio>#include <cstring>#include <cstdlib>#include <algorithm>using namespace std;const int N = 100000;int seq[N+1], num[N+1], left[N+1], right[N+1];long long dp[N+1][2];int main(){	int n;	scanf("%d", &n);	for(int i=1; i<=n; ++i)	{		scanf("%d", seq+i);		num[i] = seq[i];	}	sort(num + 1, num + n + 1);	int top = unique(num + 1, num + n + 1) - num - 1;	memset(left, 3, sizeof left);	memset(right, -1, sizeof right);	for(int i=1, p; i<=n; ++i)	{		p = lower_bound(num + 1, num + top + 1, seq[i]) - num;		if(left[p] > i)			left[p] = i;		if(right[p] < i)			right[p] = i;	}	dp[1][0] = right[1] - 1 + (right[1] - left[1]);	dp[1][1] = right[1] - 1;	for(int i=2; i<=top; ++i)	{		dp[i][0] = right[i] - left[i] + min(			dp[i-1][0] + abs(left[i-1] - right[i]),			dp[i-1][1] + abs(right[i-1] - right[i])		);		dp[i][1] = right[i] - left[i] + min(			dp[i-1][0] + abs(left[i-1] - left[i]),			dp[i-1][1] + abs(right[i-1] - left[i])		);	}	printf("%I64d/n", n + min(dp[top][0], dp[top][1]));	return 0;}