동적 계획 최적화

단조 대열
약술
함수 f[i], 이전은 다음과 같다. f[i]=min(g[j]) 중 g[j]는 j 또는 f[j]에 관한 함수이고 b[i]≤j사각형 부등식
약술
함수 f[i][j][i][j]를 다음과 같이 이전: f[i] [j][i] [i] [j], f[i] [j], f[i] [j][i] [j]min(f[i] [[[i] [k][k][k][k][k][k[[[k[[[k+1] [j]] [j]] [j]]]]의 다음과 같은 두 가지 성질: 1, a≤[[[k[k[k][k][k][k][j][j] 함수 f[i] 함수 f[j][j]를 다음과 같이 이전: f[j] 함수 f[j] 함수 f[i] 함수 f[i] [i] [j][j], 다음과 같이 다음과 같이 다음과 같이 이전: f[j[j]는 구간에 포함된 단조성과 사각형의 부등식을 만족시키고 이때 함수 f[i][j]도 사각형의 부등식을 만족시킨다.그 결정 함수 g[i][j]는 구간에 포함된 단조성을 만족시킬 것이다.우리는 g[i][j]를 이용하여 구간에 포함된 단조성이라는 성질을 만족시키고 의사결정 변수 k의 매거 범위를 축소하여 dp를 최적화할 수 있다.
몇몇 제목
최소 대가 암나무
Description
n더미의 모래가 설치되어 있어 모래 더미마다 일정한 품질이 있기 때문에 지금 n더미의 모래를 한 무더기로 합쳐야 한다. 합치는 과정은 매번 서로 인접한 두 무더기의 모래를 한 무더기로 합쳐야 한다. 이렇게 n-3을 한 번 합친 후에 한 무더기의 모래만 남는다.두 무더기의 모래의 질량과 두 무더기의 모래를 합병하는 대가로 n-3차 합병의 최소 대가를 요구한다.
Solution & Code
f[i][j]=min(f[i][k]+f[k+1][j]+sum[i][j]) 중sum[i][j]는 구간에 포함된 단조성과 사각형 부등식을 만족시키기 때문에 f[i][j]는 사각형 부등식을 만족시키고 그 결정 함수 g[i][j]는 구간에 포함된 단조성을 만족시키기 때문에 사각형 부등식으로 속도를 높일 수 있다.

#include 
#include 
using namespace std;

const int maxn = 105;
const int inf = 1e9;

int n, w[maxn], s[maxn], f[maxn][maxn], g[maxn][maxn];

int main(){

    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d", &w[i]);
    for(int i = 1; i <= n; ++i) s[i] = s[i-1] + w[i];
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            f[i][j] = inf;
    for(int i = 1; i <= n; ++i) f[i][i] = 0, g[i][i] = i;
    for(int l = 2; l <= n; ++l)
        for(int i = 1, j = i + l - 1; j <= n; ++i, ++j)
            for(int k = g[i][j-1]; k <= g[i+1][j] && k < j; ++k){
                int tmp = f[i][k] + f[k+1][j] + s[j] - s[i-1];
                if(f[i][j] > tmp){
                    f[i][j] = tmp;
                    g[i][j] = k;
                }
            }
    printf("%d
", f[1][n]);

    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

Algorithms / 백준 2667번 파이썬

링크 풀이 코드 Algorithms / 백준 2667번 파이썬...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

동적 계획 최적화

좋은 웹페이지 즐겨찾기