國家集訓(xùn)隊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.從后向前推把更大的工作量留給后面的人，標(biāo)記'/'出現(xiàn)的位置
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.如果'/'的數(shù)量小于題目給出的，從頭尋找第一個不是'/'的位置，標(biāo)記之
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轉(zhuǎn)移的時候標(biāo)記轉(zhuǎn)移方向，試圖得出標(biāo)記‘/’的位置，這個想法是錯的，仔細想一下就知道了，
再不濟AC以后再試試