$$書的復制$$

Description

現在要把m本有順序的書分給k個人復制（抄寫），每個人的抄寫速度都一樣，一本書不允許分給兩個或兩個以上的人抄寫，分給每個人的書，必須是連續的，比如不能把第一、第三、第四本書給同一個人抄寫。

現在請你設計一種方案，使得復制時間最短。復制時間為抄寫最多的人用去的時間。

Input

第一行兩個整數，m,k(k<=m<=500)

第二行為m個整數，第i個數表示第i本書的頁數。

Output

最短時間

Sample Input

9 3

1 2 3 4 5 6 7 8 9

Sample Output

17

題目大意：

用n本書，每本書都有自己的頁數（抄一頁要一個單位的時間），每個人抄的必須是連續的，而且不能把書給兩個人抄，最快多久抄完？

解題方法：

本體類似于加法最大（傳送門），它要的是時間花的最少的，我們要先求出兩個人要花的最少時間，再依次往后求

動態轉移方程：

$$f[i][k]=min(f[i][k],max(f[j][k?1],a[i]?a[j]))$$

標注：

i為求前i本書，k為k個人，j為分割線

#include<cstdio> #include<iostream> using namespace std; int n,m,x,a[502],f[502][502]; int main() {memset(f,127/3,sizeof(f));scanf("%d%d",&n,&m);for (int i=1;i<=n;i++){scanf("%d",&x);a[i]=a[i-1]+x;//前綴和，方便后面計算f[i][1]=a[i];//初始化}for (int k=2;k<=m;k++)//枚舉人for (int i=k;i<=n-m+k;i++)//枚舉前i本書for (int j=1;j<i;j++)//枚舉分割線f[i][k]=min(f[i][k],max(f[j][k-1],a[i]-a[j]));//時間是分割線兩邊最大的，左邊交給k-1個人做，右邊交給第k個人做printf("%d",f[n][m]); }

總結

以上是生活随笔為你收集整理的【动态规划】书的复制 (ssl 1203)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。