Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
AC此题分4步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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator