uva 10003 나무 막대기 선형 구간 dp

선형 dp, 구간 사상
4. 567917. 동적 전이 방정식: 구간 대가 + 이번 대가
4. 567917. 아래 표 시 된 i, j 는 모든 점 이 아니 라 절단 점 을 말한다
4. 567917. 이번 대 가 는 밑바닥 에서 직접 결과 로 돌아 갈 수 있다
4. 567917. 표준 기억 화 검색 템 플 릿 을 이용 하여 존재 하면 되 돌려 줍 니 다
제목 링크:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=19202

#include
#include
using namespace std;

#define ms(s) memset(s,0,sizeof(s))

const int maxn = 50 + 5;
int n, L, a[maxn], vis[maxn][maxn], d[maxn][maxn];

int dp(int i, int j)
{
    if(i >= j-1)
        return 0;
    if(vis[i][j])//standard memorize
        return d[i][j];
    vis[i][j] = 1;
    int& ans = d[i][j];//it is convenient to understand
    ans = -1;
    for(int k = i+1; k <= j-1; k++)
    {
        int v = dp(i,k) +dp(k,j) + a[j]-a[i];
        if(ans < 0 || v < ans)
            ans = v;
    }
    return ans;
}

int main()
{
    while(scanf("%d%d",&L, &n) == 2 && L)
    {
        for(int i = 1; i <= n; i++)
            scanf("%d",&a[i]);
        a[0] = 0;
        a[n + 1] = L;
        ms(vis);
        printf("The minimum cutting is %d.
",dp(0, n+1));
    }
    return 0;
}

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

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

선형 dp, 구간 사상 동적 전이 방정식: 구간 대가 + 이번 대가 아래 표 시 된 i, j 는 모든 점 이 아니 라 절단 점 을 말한다 이번 대 가 는 밑바닥 에서 직접 결과 로 돌아 갈 수 있다 표준 기억 화 검...

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

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

uva 10003 나무 막대기 선형 구간 dp

좋은 웹페이지 즐겨찾기