Preface
做了一道可靠大仙贝给的 SJTU 巴院的题。出题人 ****** 啊。题目表述不清。smallest to largest 不是 size 而是 index，所以这句话有什么说的必要吗?。
题面
Description
In modern data centers, people often use tape drives to store large amounts of data. There are now a total of N files numbered from 1 to N that need to be written to a single tape. The files are written in order from smallest to largest on different locations on the tape, with zero spacing between files. The size of i-the file is a_i byte
Suppose we use a tape drive with m read/write heads, any one of which can write from any position on the tape. The writing speed of the tape head is C bytes per second. These heads can not cross each other, so each read-write head can only select a continuous interval of files to write. The head is allowed to stay idle in the whole process. But one head may not halt until it has completely written all the files initiated by it to write.
We would like to know the minimum completion time for this batch of files to be completely written.
Input
The first line contains 3 integers seperated by space. They aren,mandCas described.
The second line contains n integers where the i-th integer isa_i
1<=n,m<= 1e2, 1 <=C<= 1e2, 1 <=a_i<= 1e4
Output
The integer which is the rounding up of the completion time (unit: second)
Sample Input 1
5 3 4
5 8 3 10 7
Sample Output 1
4
题解
设 $f[i][j]$ 表示前 $i$ 个文件分为 $j$ 组的最小的所有区间的最大值。
$$
f[i][j] = \min_{0 \leq k \leq i} \{\max (f[i - k][j - 1], \sum_{p=i-k+1}^i a[p])\}
$$
后面的 sigma 可以用前缀和优化
$$
\sum_{p=i-k+1}^i a[p] = s[i] - s[i - k]
$$
代码
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 1e2+5;
int a[maxn], s[maxn], f[maxn][maxn];
int up(int n, int d) {
if (n % d) return n / d + 1;
return n / d;
}
signed main() {
int n, m, C; cin >> n >> m >> C;
for (int i = 1; i <= n; i ++) cin >> a[i];
memset(f, 0x7f, sizeof(f));
for (int i = 1; i <= n; i ++) s[i] = s[i - 1] + a[i];
for (int i = 0; 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 = 0; k <= i; k ++)
f[i][j] = min(f[i][j], max(f[i - k][j - 1], s[i] - s[i - k]));
cout << up(f[n][m], C) << endl;
return 0;
}