Cutting Sticks Time Limit:3000MS Memory Limit:0KB 64bit IO Format:%lld & %llu
题目:
题目大意:
题目说的是有一根长为 l 的木棍,现在想要在其中 n 个位置切 开,但是每次切都需要花费所切的棒子的长度的钱数,求最少话多少钱。
刚开始拿到这道题,不知道怎么去解,想的是利用二分法的思想,没次取最靠近所切棍子中间的位置,但是,这样需要很大的时间,所以,肯定是不行的,看了一下大牛的博客,了解到这是属于 区间 dp 的问题,于是开始翻阅各种介绍区间dp 的资料,开始对区间dp 学习,花了将近一天的时间,终于把这道题给A 了,
说一下解题思路,解题的思路就是 每次选取一定长度的区间(长度 从 1 开始 带 l + 1),然后判断在不同的节点切开所需要的花费,这样,一直判断,求出最终的解
附上代码:
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#define INF 0x3f3f3f3f
using namespace std;
int dp[1100][1100] = {0};
int main()
{
int n,m;
while(cin >> n && n) 木棍长度为 n
{
int a[100] = {0};
cin >> m; // 要切 m 次
for(int i = 1;i <= m;i++) // 所要切的点的位置
{
cin >> a[i];
}
a[0] = 0; // 加上两端,形成这根木棍总长度的区间
a[m+1] = n;
memset(dp,0,sizeof(dp));
for(int i = 1;i <= m + 1;i++) // 区间的长度 为 i
{
for(int j = 0;j <= m + 1;j++) // 区间的开始点为 j
{
int Min = INF;
if(j + i > m + 1)
break;
for(int k = j + 1;k < j + i;k++) // 区间内的每个切点进行判断 求出最优解
{
Min = min(Min,dp[j][k] + dp[k][j + i] + a[j + i] - a[j]);
}
dp[j][j + i] = Min == INF ? dp[j][j + i] : Min; // 判断区间的最优解用不好用更新
}
}
printf("The minimum cutting is ");
cout << dp[0][m + 1] << "." << endl; // 输出 0 到 m + 1 的区间的最优解,也就是木根的区间为【0,n】的最优解,就是该长度为 n 的木棍的m次切的最优解
}
return 0;
}