UVA 10003 Cutting Sticks+区间DP

纵有疾风起

题目大意

有一个长为L的木棍，木棍中间有n个切点。每次切割的费用为当前木棍的长度。求切割木棍的最小费用

输入输出

第一行是木棍的长度L，第二行是切割点的个数n，接下来的n行是切割点在木棍上的坐标。

输出切割木棍的最小费用

前话-区间dp简单入门

区间dp的入门下面博客写的非常好，我就是看的他们博客学会的，入门简单，以后的应用就得靠自己了。

https://blog.csdn.net/qq_41661809/article/details/81487613 看懂了，基础入门

https://blog.csdn.net/qq_40772692/article/details/80183248 略微进阶些

https://www.cnblogs.com/HDUjackyan/p/9123199.html 专题训练+代码实现

解题思路

1. 使用动态规划，定义\(dp[\ i\ ][\ j\ ]\)为切割木棍\(i-j\)的最优费用，然后使用区间dp来进行处理
2. 或则使用搜索算法进行，但是为了降低复杂度，一般会使用记忆化搜索。

代码

// 动态规划解法

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

const int inf=0x3f3f3f3f;

int cut[100];

int dp[100][100];

int main()

{

	int L, n;

    while(scanf("%d",&L) && L)

    {

    	memset(dp, inf, sizeof(dp));

        cin>>n;

	    for(int i=1; i<=n; i++){

	        cin>>cut[i];

	    }

	    cut[0]=0;

	    cut[n+1]=L;

	    for(int i=0; i<=n; i++)

            dp[i][i+1]=0; //相邻两个切割点之间是一段木棍，根据dp的含义，它们的值为零

		for(int len=2; len<=n+1; len++) //枚举区间长度，从长度为2开始

		{

	        for(int i=0; i+len<=n+1; i++) //起点要从0开始

			{

	            int j=i+len; //终点

				for(int k=i+1; k<j; k++) //枚举断点

				{

	                dp[i][j]=min(dp[i][k]+dp[k][j]+cut[j]-cut[i], dp[i][j]);

	            }

	        }

	    }

	    cout<<"The minimum cutting is "<<dp[0][n+1]<<"."<<endl;

    }

    return 0;

}

//记忆化搜索  搜索真万能！！！

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int N = 1010;

const int INF = 0x3f3f3f3f;

int c[N] ,dp[N][N];

int len , n;

int d(int l, int r) {

	if(r - l == 1) {

		return 0;

	}

	if(dp[l][r] > 0) {

		return dp[l][r]; //算过>0，就不要重新再算了

	}

	dp[l][r] = INF;

	for(int i = l; i <= r; i++) {

		dp[l][r] = min( dp[l][r], d(l,i)+d(i,r) + c[r] - c[l]);

	}

	return dp[l][r];

}

int main() {

	while(scanf("%d",&len) != EOF && len) {

		scanf("%d",&n);

		for(int i = 1; i <= n; i++) {

			scanf("%d",&c[i]);

		}

		c[0] = 0;

		c[n+1] = len;

		memset(dp,0,sizeof(dp));

		int ans = d(0, n+1);

		printf("The minimum cutting is %d.\n",ans);

	}

	return 0;

}

//---------------------

//作者：HelloWorld10086

//来源：CSDN

//原文：https://blog.csdn.net/HelloWorld10086/article/details/40626461

//版权声明：本文为博主原创文章，转载请附上博文链接！