UVA 10003 Cutting Sticks(구간 dp)

6007 단어 dp
제목 링크: UVA - 10003 Cutting Sticks

제목의 뜻


길이가 L인 막대기와 n개의 절단점을 주고 매번 절단하는 대가가 현재의 막대기의 길이이며 가장 적은 총 절단 대가가 얼마인지 물어본다.

사고의 방향


전형적인 구간 dp[i][j]=min(dp[i][k]+dp[k][j]+a[j]-a[i]))|i

코드


점차 미루다

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cmath>

using namespace std;
const int N = 59;
int a[N];
int dp[N][N];

int main()
{
    int l;
    while(~scanf("%d", &l) && l)
    {
        int n;
        memset(dp, 0x3f, sizeof(dp));
        scanf("%d", &n);
        for(int i=1; i<=n; i++)
        {
            dp[i-1][i] = 0;
            scanf("%d", &a[i]);
        }
        dp[n][n+1] = 0;
        a[0] = 0;
        a[n+1] = l;
        for(int len=2; len<=n+1; len++)
            for(int i=0; i+len<=n+1; i++)
                for(int k=i+1; k<i+len; k++)
                    dp[i][i+len] = min(dp[i][i+len], dp[i][k]+dp[k][i+len]+a[i+len]-a[i]);
        printf("The minimum cutting is %d.
"
, dp[0][n+1]); } return 0; }

기억화 검색

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cmath>

using namespace std;
const int N = 59;
int a[N];
int dp[N][N];

int dfs(int i, int j)
{
    if(dp[i][j] != -1)
        return dp[i][j];
    int ans = 0x3f3f3f3f;
    for(int k=i+1; k<j; k++)
        ans = min(ans, dfs(i,k)+dfs(k,j)+a[j]-a[i]);
    return dp[i][j] = ans;
}

int main()
{
    int l;
    while(~scanf("%d", &l) && l)
    {
        int n;
        memset(dp, -1, sizeof(dp));
        scanf("%d", &n);
        for(int i=1; i<=n; i++)
        {
            scanf("%d", &a[i]);
            dp[i-1][i] = 0;
        }
        dp[n][n+1] = 0;
        a[0] = 0;
        a[n+1] = l;
        printf("The minimum cutting is %d.
"
, dfs(0, n+1)); } return 0; }

좋은 웹페이지 즐겨찾기