louisfghbvc的部落格

題目連結:   https://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=30012

題目大意:  任意切木棍，求最小切木棍的總和值。

思路:  記憶化搜索，首先加入0跟木棍長度len，幫助計算花費，如果長度<2回傳0，枚舉(L, R)區間切木塊，分成2等分，合併。

注意這題cin放在while會超時，=.=完全不懂，還是scanf好用很多。

代碼:  

#include <bits/stdc++.h>
#define N 55
using namespace std;

int arr[N];
int dp[N][N];
int l, n;
int dfs(int L, int R){
    if(R - L < 2) return 0;
    if(dp[L][R] != -1) return dp[L][R];
    int res = INT_MAX;
    for(int i = L+1; i < R; ++i){
        int cost = arr[R]-arr[L];
        res = min(res, cost + dfs(L, i) + dfs(i, R));
    }
    return dp[L][R] = res;
}

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

/**
100
3
25 50 75
10
4
4 5 7 8
0
**/