poj1160 Post Office 사각형 부등식 최적화

2506 단어 poj동적 기획
사각형 부등식의 동적 기획 최적화 알고리즘은 말할 것도 없고 그것에 대해 간단한 소개만 한다. 이것은 동적 기획 알고리즘의 시간 복잡도를 최적화하는 방법 중 하나이고 공간 복잡도는 몇 개의 상수만 증가할 뿐 고려할 필요가 없다.방법은 솔직히 말하면 검증이 매우 번거롭기 때문에 나는 문제풀이를 보고 다시 알아야 할 때가 많다. 여기서도 더 이상 말하지 않겠다.직접 부호:
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;

#define REP(i, a, b) for(i = (a);i <= (b); ++i)

const int INF = 1000000000;
const int maxn = 500;

int n, m;
int a[maxn], d[maxn][maxn], dp[maxn][maxn];

int main() {
    int i, j, k;
    scanf("%d", &n);
    scanf("%d", &m);
    REP(i, 1, n)
        scanf("%d", &a[i]);
    REP(i, 1, n)
        REP(j, i + 1, n) {
            int mid = (i + j) >> 1;
            REP(k, i, j)
                d[i][j] += abs(a[k] - a[mid]);
        }
    REP(i, 1, m)
        REP(j, 1, n)
            dp[i][j] = INF;
    REP(i, 1, n)
        dp[1][i] = d[1][i];
    REP(i, 2, m)
        REP(j, i, n)
            REP(k, 1, j)
                if(dp[i][j] > dp[i - 1][k] + d[k + 1][j])  
                    dp[i][j] = dp[i - 1][k] + d[k + 1][j]; 
    printf("%d
", dp[m][n]);
    return 0;
}
Wicket에서 사용할 수 있는 차트 표시 라이브러리 WickedChart
데이터 구조 (1): 선형 표 의 순서 표시 와 실현

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage