Description
Kirill the gardener has got a new task. He has to water the flowers growing on the huge flowerbed! It should be mentioned that the bed is very long and narrow at the same time. So from bird’s-eye view (and Kirill growth too) it looks like a straight line, where n points-flowers are located at regular intervals. For this job Kirill has a watering pot of infinite volume and smartwatch that shows moisture content of each flower before watering. The watering takes too much time, so the most dried flowers can die, which is unacceptable. So Kirill decided to water the flowers in order of their non-decreasing dryness. On the other hand, he wants to finish the watering as soon as possible, because there are a lot of other interesting things.
Assume that watering of one flower and walking between two neighbor flowers takes Kirill one minute. Can you figure out the time in which the young gardener will complete his job if he acts optimally? Initially Kirill stands near the leftmost flower.
The first line contains an integer n (1≤n≤105) — it’s amount of flowers in the flowerbed. The second line contains n integers separated by spaces — it‘s moisture content of flowers given in order of their positions in the flowerbed from left to right. Moisture content is an integer from 1 up to 109 (including both).
Output
In the only line PRint an integer — the minimal time in which Kirill would complete watering.
題意
給定一個 n ，以及編號為 1-n 的 n 個數字。已知起點為 1 ，假設移動一個位置花費的時間為 1 ，對某位置的數作處理花費的時間為 1 ，要求必須若仍存在未處理且比當前位置上的數更小的數字，則不能處理當前位置的數，在選擇最優策略的情況下，問處理完 n 個數的最小時間。
分析
顯然，每個數都必須處理一遍，則時間 n 的花費是必須的。
根據題意可以知道每次處理的數一定是當前未處理數中最小的數（可能有多個數同時最小）。在單次處理值為 x 的數時，為了使花費時間最小，必然是從同樣值為 x 的最左坐標向最右坐標移動，或從最右坐標向最左坐標移動。
考慮從上一個大小的值（最左坐標和最右坐標分別為 li,ri ）到處理下一個值（最左坐標和最右坐標分別為 li+1,ri+1 ），在保證上一個處理中移動最優的情況下，為處理下一個值的移動必然符合
dp[i][1]dp[i][0]=min(dp[i?1][0]+abs(li?1?li),dp[i?1][1]+abs(ri?1?li))=min(dp[i?1][0]+abs(li?1?ri),dp[i?1][1]+abs(ri?1?ri)) 其中 dp[i][0] 表示在結束第 i 大的值的操作后處于該值最左端點的最小時間，dp[i][1] 表示在結束第 i 大的值的操作或處于該值最右端點的最小時間。
代碼
#include<bits/stdc++.h>using namespace std;const int N = 100000 + 10;struct Node { int dry, idx;}p[N];bool Operator<(Node a,Node b) { if(a.dry == b.dry) return a.idx < b.idx; return a.dry < b.dry;}long long myabs(long long a) { return a > 0 ? a : -a;}long long dp[N][2];int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&p[i].dry), p[i].idx = i; sort(p+1, p+n+1); int pos = 1; long long cnt = n; vector< pair<long long, long long> > vec; for(int i=1, l, r;i<=n;i++) { l = p[i].idx; r = p[i].idx; for(i++;i<=n;i++) { if(p[i].dry == p[i-1].dry) r = p[i].idx; else{ i--; break; } } vec.push_back(make_pair(l,r)); cnt += r-l; } dp[0][1] = myabs(vec[0].first - 1ll); dp[0][0] = myabs(vec[0].second - 1ll); for(int i=1;i<vec.size();i++) { dp[i][1] = min( myabs(vec[i-1].first - vec[i].first) + dp[i-1][0], myabs(vec[i-1].second - vec[i].first) + dp[i-1][1]); dp[i][0] = min( myabs(vec[i-1].first - vec[i].second) + dp[i-1][0], myabs(vec[i-1].second - vec[i].second) + dp[i-1][1]); } printf("%I64d/n", min(dp[vec.size()-1][0], dp[vec.size()-1][1]) + cnt);}
