UVA10003 - Cutting Sticks

2479 단어
dp(i, j)로 나무 막대기가 i절단점과 j절단점 사이의 최소 비용 상태 이동 방정식을 나타낸다. dp(i, j)=min(dp(i, j), dp(i, h)+dp(j, h)+num[j]-num[i]).
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

#define INF 1 << 30
int dp[55][55];
int num[55], n;
int main()
{
   // freopen("in.txt", "r", stdin);
    int l;

    while(cin >> l && l)
    {
        cin >> n;
        for(int i = 1; i <= n; i++)
            scanf("%d", num+i);
        num[0] = 0;
        num[n+1] = l;
       for(int i = 2; i <= n+1; i++)
        for(int j = 0; j + i <= n+1; j++)
       {
           dp[j][i+j] = INF;
           for(int h = j+1; h < j+i; h++)
           {
              dp[j][i+j] = min(dp[j][i+j], dp[j][h] + dp[h][i+j] + num[i+j] - num[j]);
           }
       }
        printf("The minimum cutting is %d.
"
, dp[0][n+1]); } return 0; }

좋은 웹페이지 즐겨찾기