首页 > 代码库 > Cutting Sticks

Cutting Sticks

2024-07-14 05:43:14   221人阅读

uva10003:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=944

题意：给你一个木棍，然后让你切n刀，每次切都会有一个费用。例如，假如说一开始木棍长是10，然后要你在2,3,5三处切3刀，第一次切2的话，会花费10，然后切3的话会花费8，剩余的长度是7，所以第3刀会花费7，所以一共花费25，现在要你求一个最小的花费。

题解：一开始想着贪心，每次让剩余的最长的木棍最短，其实这样的贪心是错误的。第二组样例都过不了。所以果断是DP。接着想DP方程，想了很久，都没有想到，但是最后想了一个dp[i][j]表示从第i到j这么长的距离所花费的最小费用，这样只要枚举i,j之间的数就可更新dp[i][j]，其实这样的思想，我是受到最短路(spfa)的启发才想到的。接着就是i,j怎么枚举的问题，由于最后的答案是dp[0][n+1],所以外层是for(i),从大到小，接着是j,应该从小到大。这里只要记录切的位置和起点和终点即可，不用开dp[1002][1002],只要开dp[56][56]这么大的数组即可，枚举的时候也节省时间，否则会T的。

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int inf=100000000; 7 int dp[52][52]; 8 int a[52],n,len; 9 int main(){10   while(~scanf("%d",&len)&&len){11      scanf("%d",&n);12      for(int i=0;i<=52;i++){13         for(int j=0;j<=52;j++)14              dp[i][j]=inf;15      }16      dp[0][1]=0;17      for(int i=1;i<=n;i++){18          scanf("%d",&a[i]);19         dp[i-1][i]=0;20      }21      a[0]=0;22      a[n+1]=len;23      dp[n][n+1]=0;24       for(int i=n+1;i>=0;i--){25          for(int k=i;k<=n+1;k++)26            for(int j=1;j<=n;j++){27              if(j>i&&j<k)28                 dp[i][k]=min(dp[i][k],dp[i][j]+dp[j][k]+a[k]-a[i]);29           }30       }31       printf("The minimum cutting is %d.\n",dp[0][n+1]);32   }33 34 }
View Code

 

Cutting Sticks


联系
我们