POJ3666(dp)

Description A straight dirt road connects two fields on FJ’s farm, but it changes elevation more than FJ would like. His cows do not mind climbing up or down a single slope, but they are not fond of an alternating succession of hills and valleys. FJ would like to add and remove dirt from the road so that it becomes one monotonic slope (either sloping up or down). You are given N integers A1, … , AN (1 ≤ N ≤ 2,000) describing the elevation (0 ≤ Ai ≤ 1,000,000,000) at each of N equally-spaced positions along the road, starting at the first field and ending at the other. FJ would like to adjust these elevations to a new sequence B1, . … , BN that is either nonincreasing or nondecreasing. Since it costs the same amount of money to add or remove dirt at any position along the road, the total cost of modifying the road is |A1 - B1| + |A2 - B2| + … + |AN - BN | Please compute the minimum cost of grading his road so it becomes a continuous slope. FJ happily informs you that signed 32-bit integers can certainly be used to compute the answer. Input Line 1: A single integer: N Lines 2..N+1: Line i+1 contains a single integer elevation: Ai Output Line 1: A single integer that is the minimum cost for FJ to grade his dirt road so it becomes nonincreasing or nondecreasing in elevation. Sample Input 7 1 3 2 4 5 3 9 Sample Output 3
먼저 욕심을 생각해 보자. 답안을 최소화하는 방안이 존재하기 때문에 B수조에 나타난 숫자가 AA에 나타난 것은 분명하고 증명할 수 있다. 그러면 우리는 A수조를 순서(오름차순과 내림차순을 각각 한 번씩)만 배열하고 순서를 찍은 수조는 C수조로 상태fi, jfi, j는 현재 i위를 고려하고 있음을 나타낸다. C수조에 j수조의 답안의 최소값을 넣으면fi,j=min1<=k<=j f i, j = m i n 1 <=k <=j {fi --1, k f i --1, k} +| | ai --b j | a i --b j | min m i n 안쪽 부분은 LCIS L I S 처리 방법을 본떠서 j를 일일이 들 때 극치를 유지하는 것이 분명히 dp d p의 첫 번째는 생략할 수 있는 것이다
토로:usaco 데이터 진수, 강하 순서 없이 모두 A

#include
using namespace std;
#define rep(i,j,k) for(int i = j;i <= k;++i)
#define repp(i,j,k) for(int i = j;i >= k;--i)
#define rept(i,x) for(int i = linkk[x];i;i = e[i].n)
#define P pair
#define Pil pair
#define Pli pair
#define Pll pair
#define pb push_back 
#define pc putchar
#define mp make_pair
#define file(k) memset(k,0,sizeof(k))
#define ll long long
namespace fastIO{
    #define BUF_SIZE 100000
    #define OUT_SIZE 100000
    bool IOerror = 0;
    inline char nc(){
        static char buf[BUF_SIZE],*p1 = buf+BUF_SIZE, *pend = buf+BUF_SIZE;
        if(p1 == pend){
            p1 = buf; pend = buf+fread(buf, 1, BUF_SIZE, stdin);
            if(pend == p1){ IOerror = 1; return -1;}
        }
        return *p1++;
    }
    inline bool blank(char ch){return ch==' '||ch=='
'||ch=='\r'||ch=='\t';}
    inline void read(int &x){
        bool sign = 0; char ch = nc(); x = 0;
        for(; blank(ch); ch = nc());
        if(IOerror)return;
        if(ch == '-') sign = 1, ch = nc();
        for(; ch >= '0' && ch <= '9'; ch = nc()) x = x*10+ch-'0';
        if(sign) x = -x;
    }
    inline void read(ll &x){
        bool sign = 0; char ch = nc(); x = 0;
        for(; blank(ch); ch = nc());
        if(IOerror) return;
        if(ch == '-') sign = 1, ch = nc();
        for(; ch >= '0' && ch <= '9'; ch = nc()) x = x*10+ch-'0';
        if(sign) x = -x;
    }
    #undef OUT_SIZE
    #undef BUF_SIZE
};
using namespace fastIO;
int n;
ll ans;
int a[2010];
int b[2010];
ll f[2010];
int main()
{
    read(n);
    rep(i,1,n) read(a[i]),b[i] = a[i];
    sort(b+1,b+n+1);
    memset(f,20,sizeof(f));ans = f[0];
    f[1] = 0;
    rep(i,1,n)
    {
        ll val = f[1];
        rep(j,1,n)
        {
            val = min(val,f[j]);
            f[j] = val + abs(a[i]-b[j]);
        }
    }
    rep(i,1,n) ans = min(ans,f[i]);
    memset(f,20,sizeof(f));
    f[n] = 0;
    rep(i,1,n)
    {
        ll val = f[n];
        repp(j,n,1)
        {
            val = min(val,f[j]);
            f[j] = val + abs(a[i]-b[j]);
        }
    } 
    rep(i,1,n) ans = min(ans,f[i]);
    printf("%lld
",ans);
    return 0;
}