BZOJ1575 USACO 2009 Jan Gold 2.The Baric Bovine

제의:스스로 뇌보.
Sol: 물 dp, 두 개의 새로운 단점 0, n+1을 쉽게 처리하기 위해 dp[i][j]를 설정하면 i로 끝내고 j가 있을 때 가장 좋은 값을 나타낸다.이전이 분명하다.시간 복잡도 dp와 예처리는 모두 O(n^3)이다.
Code:

#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
#include <cstdlib>
using namespace std;
 
typedef long long LL;
 
#define N 110
int w[N];
 
LL pre[N][N], dp[N][N];
 
#define _abs(x) ((x)>0?(x):(-(x)))
int main() {
    int n, lim;
    scanf("%d%d", &n, &lim);
     
    register int i, j, k;
    for(i = 1; i <= n; ++i)
        scanf("%d", &w[i]);
         
    for(i = 0; i <= n; ++i) {
        for(j = i + 1; j <= n + 1; ++j) {
            if (i == 0)
                for(k = i + 1; k < j; ++k)
                    pre[i][j] += 2 * _abs(w[k] - w[j]);
            else if (j == n + 1)
                for(k = i + 1; k < j; ++k)
                    pre[i][j] += 2 * _abs(w[i] - w[k]);
            else
                for(k = i + 1; k < j; ++k)
                    pre[i][j] += _abs(2 * w[k] - w[i] - w[j]);
        }
    }
    pre[0][n + 1] = 1LL << 60;
     
    memset(dp, 0x3f, sizeof(dp));
    dp[0][1] = 0;
    for(j = 2; j <= n + 2; ++j)
        for(i = j - 1; i <= n + 1; ++i)
            for(k = 0; k < i; ++k)
                dp[i][j] = min(dp[i][j], dp[k][j - 1] + pre[k][i]);
     
    for(i = 3; i <= n + 2; ++i) {
        if (dp[n + 1][i] <= lim) {
            printf("%d %lld
", i - 2, dp[n + 1][i]);
            return 0;
        }
    }
     
    return 0;
}