UVA10003题解

caotianhao · 2023-07-12 20:54:41 · 题解

插句题外话

本蒟蒻第 2 次写题解；
看到这题我居然想到了 POJ1159（都是区间 DP）；
不会记搜好吧（~~暴搜都不会~~），DP 大法好啊。
题目翻译

传送门
你得把一根木棍砍成几段。根据被切割的木棍的长度收费。他们的工作程序要求他们一次只切一刀。很容易注意到，在切割顺序上的不同选择可能导致不同的价格。例如，考虑一根长度为 10 米的棍子，2 米，4 米和 7 米处可以被切割。有几种选择。我们可以先从 2 点开始切割，然后是 4 点，然后是 7 点。这导致了 10 + 8 + 6 = 24 的价格，因为第一根棍子的长度是 10 米，结果是 8，最后一根是 6。另一个顺序是 4，2，7。这将导致 10 + 4 + 6 = 20，这是一个更好的价格。你的老板信任你的计算机能力，相信你能找出切一根给定的棍子所需的最低成本。

题目大意

就是切一根木棍，长度为 l，有 n 个要切的点，分别为距离起点长 a_1,a_2……a_n 的点（递增排序）。每切一次，需要花等同于切之前木棍的长度的钱，问最小花费。
切之前长度：以翻译的第 2 个样例为例，第 1 次切，长度为 10；第 2 次切，长度为 4（4 号点切断了，分成 4 和 6 两部分，切 2 在 4 的那部分）；第 3 次切，长度为 6（同上，切 7 在 6 的那部分）。

解题思路

DP 要素之一——状态定义

刚刚也说了，这题是区间 DP，那状态就很简单
### DP 要素之二——状态转移我们可以枚举区间（$i,j$）和区间中的切点（$k$），然后推出转移方程： $dp_{i,j}=\min(dp_{i,j},dp_{i,k}+dp_{k,j}+(a_j-a_i)) 但是我们会发现一个问题，在算 $dp_{i,j}$ 时，$dp_{k,j}$ 还没算。所以我们改为枚举区间起始点和区间长度（结点个数）。 ### DP 要素之三——状态初始化
如果中间截不了了（dp_{i,i+1}），赋值为 0；

加上起始结点（a_0=0）和末结点（a_{n+1}=l）；

解决完 DP，剩下的就都是细节问题了，会在代码中一一展示。

ACcode

#include<bits/stdc++.h>
using namespace std;
int l,n,a[1005],dp[55][55];
const int INF=0x3f3f3f3f;
int main(){
 while(scanf("%d",&l)==1){//多组输入数据 
     if(l==0){
         break;
     }
     memset(dp,INF,sizeof(dp));//细节1：初始化为INF，因为后面要求min 
     scanf("%d",&n);
     for(int i=1;i<=n;i++){
         scanf("%d",&a[i]);
         dp[i][i+1]=0;
     }
     a[n+1]=l;//加末结点（想一想，为什么不用加起始结点） 
     dp[0][1]=0;//细节2：dp[i][i+1]初始化的时候从1开始，没加dp[0][1] 
     for(int cnt=2;cnt<=n+1;cnt++){//细节3：枚举结点个数时，一个区间至少2个结点，至多n+1个结点 
         for(int i=0;i+cnt<=n+1;i++){//细节4：枚举起始结点要注意从0开始和末结点不能超过n+1 
             int j=i+cnt;//计算末结点 
             for(int k=i+1;k<=j-1;k++){//细节5：切的点不能是起始结点和末结点 
                 dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+(a[j]-a[i]));//转移方程 
             }
         }
     }
     printf("The minimum cutting is %d.\n",dp[0][n+1]);//输出，注意.和换行（vj上在这错了2遍） 
 }
 return 0;
}

UVA10003题解

插句题外话

题目翻译

题目大意

解题思路

DP 要素之一——状态定义

加上起始结点（a_0=0）和末结点（a_{n+1}=l）；

ACcode