bet365体育app下载_外围bet365 网址_bet365娱乐在线先锋网?bet365体育app下载_外围bet365 网址_bet365娱乐在线片段及技术文章聚合

UVA10003 Cutting Sticks

题目大意

一根长度位L的木棍上有n个切割点,这个木棍做n次切割,求总花费最少是多少。每次花费为被切割木棍的长度。如L=10,切割点为2,4,7。一次切割2,4,7,总花费=10+8+6=24;

解题思路

这是一道类似矩阵连乘的题目,套用模板就行了。先求小区间的最小花费,然后根据小区间推得大区间的最小花费。

参考bet365体育app下载_外围bet365 网址_bet365娱乐在线

#include
#include
#include
using namespace std;
const int inf = 0x3f3f3f3f;
int L,n;
int l[55];  //表示第i个点的位置  
int dp[55][55]; //表示切割第i~j段最小花费 ,从0开始 
                //注意这里表示两段间而不是两点间 
int main(){
    while (cin >> L,L){
        cin >> n;
        l[0]=0;
        for(int i=1; i<=n; i++)
            cin >> l[i];
        l[n+1]=L;
        memset(dp,inf,sizeof(dp));
        for(int i=0; i<=n; i++) dp[i][i]=0;
        for(int i=1; i<=n; i++)
            for(int j=0; j+i<=n; j++){
                int t=j+i;
                dp[j][t] = l[t+1]-l[j]+dp[j][t-1];
                for(int k=j; k

原文地址:UVA10003 Cutting Sticks