Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

AC此题分4步

Posted by schindlerlee at 2009-09-16 01:26:24 on Problem 1505
1.dp ,算最小完成时间, 文国家集训队2000论文集/方奇的论文种貌似把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]);

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator