AT_joi2010ho_b 题解
Ahws_rwhy
·
·
题解
标签：动态规划（dp）。
可设 dp1_i 表示前 i 个位置中，第一个人所需的最小时间，dp2_j 表示前 j 个位置中，第二个人所需的最小时间。
因为在切割的过程中，第一个人和第二个人交替进行切割。第一个人选择切割位置 $i$ 时，第二个人在位置 $j$ 上进行切割。因此，第一个人的最小时间等于 $dp2_j + T_{i+j}$，而第二个人的最小时间等于 $dp1_i + T_{i+j}$。
所以动态规划方程如下：
$$
dp1_i = \min(dp1_i, dp2_j + T_{i+j}),
dp2_j = \min(dp2_j, dp1_i + T_{i+j})
$$
最终答案为 $dp1_{n/2}$。
（upd:抱歉手打错了！）
code:
```
dp1[0]=0,dp2[0]=0;
for(int i=0; i<=n/2; i++)
for(int j=0; j<=n/2; j++) {
dp1[i]=min(dp1[i],dp2[j]+T[i+j]);
dp2[j]=min(dp2[j],dp1[i]+T[i+j]);
}
cout<<dp1[n/2]<<endl;
```