国家集训队2000论文集/方奇论文中的一题
1.dp ,算最小完成时间， 论文中貌似把max写成min了。。
二分求最小完成时间亦可，而且更快，谁让咱们看了论文了呢
for(i = 1;i <= n;i++) {
dp[1][i] = sum[1][i];
}
for(i = 2;i <= m;i++) {
for(j = 1;j <= n;j++) {
dp[i][j] = inf;
}
}
for(i = 2;i <= m;i++) {
for(j = i;j <= n;j++) {
for(k = 1;k < j;k++) { // 至少抄一本
int t = max( dp[i-1][k] , sum[k+1][j]);
if(dp[i][j] > t) {
dp[i][j] = min(dp[i][j] ,t);
}
}
}
}
2.从后向前推把更大的工作量留给后面的人，标记'/'出现的位置
int limit = dp[m][n],sum,cnt;
pre[n] = 0,cnt = 1;
for(i = n-1,sum = num[n];i > 0;i--) {
if(sum + num[i] > limit) {
pre[i] = 1;
cnt ++;
sum = num[i];
}else {
pre[i] = 0;
sum += num[i];
}
}
3.如果'/'的数量小于题目给出的，从头寻找第一个不是'/'的位置，标记之
for(i = 1,j = cnt;j < m && i <= n;i++) {
if(pre[i] == 0) {
pre[i] = 1;
j++;
}
}
4.输出
for(i = 1;i < n;i++) {
printf("%d ",num[i]);
if(pre[i])
printf("/ ");
}
printf("%d\n",num[i]);
注意：不要尝试再dp转移的时候标记转移方向，试图得出标记‘/’的位置，这个想法是错的，仔细想一下就知道了，
再不济AC以后再试试