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;}