奶牛逃跑_紀中1765_dp

題目描述

農夫約翰忘記将栅欄的一個洞修複了，導緻了他的奶牛們都逃跑了。不僅如此，奶牛們還都在搞破壞。每一隻在栅欄外的奶牛每分鐘搞的破壞都要造成約翰1塊錢的損失。是以，約翰必須去抓捕這些奶牛。幸運的是，奶牛們所在的位置都是在栅欄外的同一條直線上（每隻奶牛的位置不同）。約翰知道每隻奶牛的位置Pi，目前約翰所在的位置是0。約翰每分鐘移動一個機關的距離，并且能夠迅速的抓到所在位置的奶牛。

請幫助約翰計算他抓住這些奶牛的過程中最少會造成多少損失。

輸入

第一行一個正整數N，表示有N隻奶牛。

接下來N行，每行一個整數Pi，表示第i隻奶牛所在的位置。

輸出

輸出抓所有的奶牛的過程中會造成的最小損失。

資料範圍限制

資料範圍：1<=N<=1000，-500000<=Pi<=500000。

題解

似曾相識的題目是的你沒看錯這就是之前做過的大爺關燈的翻版還水很多

不同之處在于我們需要對奶牛的位置排序并人工放一隻奶牛在0。相對位置求出來了就能愉快地dp了

這題沒有功率的條件，那就全都是1了。需要注意的是在fj 大爺抓到第i個奶牛 關燈時這頭牛還是會搗亂的

考慮過滾數組但是仔細想了想不行呢，

方程自己想一想就能推出來的不放了

sublime-snippet賽高

Code

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <fstream>
#define debug puts("-----")
#define rep(i, st, ed) for (int i = st; i <= ed; i += 1)
#define drp(i, st, ed) for (int i = st; i >= ed; i -= 1)
#define fill(x, t) memset(x, t, sizeof(x))
#define min(x, y) x<y?x:y
#define max(x, y) x>y?x:y
#define PI (acos(-1.0))
#define EPS (1e-8)
#define INF (1<<30)
#define N 1011
#define E N * 8 + 1
#define L 255
using namespace std;
int pos[N], f[N][N][];
inline int read(){
    int x = , v = ;
    char ch = getchar();
    while (ch < '0' || ch > '9'){
        if (ch == '-'){
            v = -;
        }
        ch = getchar();
    }
    while (ch <= '9' && ch >= '0'){
        x = (x << ) + (x << ) + ch - '0';
        ch = getchar();
    }
    return x * v;
}
inline int dis(int x, int y){
    return fabs(pos[x] - pos[y]);
}
int main(void){
    freopen("cowrun.in", "r", stdin);
    freopen("cowrun.out", "w", stdout);
    int n = read();
    rep(i, , n){
        pos[i] = read();
    }
    pos[++ n] = ;
    sort(pos + , pos + n + );
    int st = ;
    rep(i, , n){
        if (!pos[i]){
            st = i;
            break;
        }
    }
    fill(f, );
    f[st][st][] = f[st][st][] = ;
    drp(i, st, ){
        rep(j, st, n){
            f[i][j][] = min(f[i][j][], f[i + ][j][] + dis(i, i + ) * (n - j + i));
            f[i][j][] = min(f[i][j][], f[i + ][j][] + dis(i, j) * (n - j + i));
            f[i][j][] = min(f[i][j][], f[i][j - ][] + dis(i, j) * (n - j + i));
            f[i][j][] = min(f[i][j][], f[i][j - ][] + dis(j - , j) * (n - j + i));
        }
    }
    printf("%d\n", min(f[][n][], f[][n][]));
    return ;
}