题意就是给出棍子的长度和n个切点,让你把它切成n+1段,每次切时花费价值为此时棍子的长度,问怎样切才能使最终花费最少。
区间dp,就是指一整段区间的最优值可以由其中几段小区间的最优值来决定,因此次类问题一般都是从小到大枚举区间的大小,然后再求每一个该大小的区间的最优值,最终得到整个区间的最优值。
#include<iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int cut[55],dp[55][55];
int main()
{
int l,n;
while(cin>>l)
{
if(l==0)
break;
cin>>n;
memset(dp,0,sizeof(dp));
cut[0]=0;
cut[n+1]=l;
for(int i=1;i<=n;i++)
cin>>cut[i];
for(int k=2;k<=n+1;k++)
{
for(int i=0;i<=n-1;i++)
{
int j=i+k;
if(j>n+1)
break;
for(int t=i+1;t<j;t++)
if(!dp[i][j])
dp[i][j]=dp[i][t]+dp[t][j]+cut[j]-cut[i];
else
dp[i][j]=min(dp[i][j],dp[i][t]+dp[t][j]+cut[j]-cut[i]);
}
}
cout<<"The minimum cutting is "<<dp[0][n+1]<<"."<<endl;
}
return 0;
}