原题网址
由于某些原因，这个网址会进不去…
题目描述
现在要把
m
m
m本有顺序的书分给
k
k
k个人复制（抄写），每个人的抄写速度都一样，一本书不允许分给两个或两个以上的人抄写，分给每个人的书，必须是连续的，比如不能把第一、第三、第四本书给同一个人抄写。
现在请你设计一种方案，使得复制时间最短。复制时间为抄写最多的人用去的时间。
格式
输入格式
第一行两个整数，
m
,
k
(
k
≤
m
≤
500
)
m,k(k\le m\le 500)
m,k(k≤m≤500) ，
第二行为
m
m
m个整数，第
i
i
i个数表示第
i
i
i本书的页数。
输出格式
最短时间。
样例
输入样例
9 3
1 2 3 4 5 6 7 8 9
输出样例
17
解题思路
设
f
[
n
,
k
]
f[n,k]
f[n,k]表示前
n
n
n本书交由
k
k
k个人抄写需要的最短时间，则状态转移方程为：
f
(
n
,
k
)
=
m
i
n
{
m
a
x
{
f
(
i
,
k
?
1
)
,
∑
j
=
i
+
1
n
}
,
i
=
1
,
2
,
.
.
.
,
n
?
1
}
f(n,k)=min\{max\{f(i,k-1),\sum^n_{j=i+1}\},i=1,2,...,n-1\}
f(n,k)=min{max{f(i,k?1),∑j=i+1n?},i=1,2,...,n?1}
状态数为
n
×
k
n\times k
n×k，转移代价为
O
(
n
)
O(n)
O(n)，故时间复杂度为
O
(
n
2
×
k
)
O(n^2\times k)
O(n2×k)
动态规划仅仅求出了最优值，如果要输出具体方案，可以根据动态规划求出的最优解做一个贪心设计：按顺序将书分配给
k
k
k个人，从第一个开始，若还能抄就继续给，此后同理，直到第
k
k
k个，方案即出，
O
(
n
)
O(n)
O(n)。
Code
#include<iostream>
#include<istream>
#include<ostream>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#include<vector>
using namespace std;
const int maxn=1000;
int n,m,a[maxn+1],f[maxn+1][maxn+1],s[maxn+1];
void init() {
ios::sync_with_stdio(false);
cin.tie();
cin>>n>>m;
for(int i=1;i<=n;i++) {
cin>>a[i];
s[i]=s[i-1]+a[i];
}
}
int main() {
init();
memset(f, 114514, sizeof(f));
for(int i=1;i<=n;i++)
f[i][1]=s[i];
for(int i=1;i<=n;i++) {
for(int j=2;j<=m;j++) {
for(int k=1;k<i;k++) f[i][j]=min(max(f[k][j-1],s[i]-s[k]),f[i][j]);
}
}
cout<<f[n][m];
return 0;
}
|