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

用DP都超时了。。。哪位大牛帮忙讲解一下,不甚感激。。(内附代码)

Posted by nicky323 at 2008-02-02 12:32:40 on Problem 1014
#include<iostream>
using namespace std;

char value[60005];

int main(){
	int i, j, k, score, record = 0;
	int num[7];
	score = 0;
	for(i = 1; i <= 6; ++i){
		scanf("%d", num + i);
		score += i * num[i];
	}
	while(score){
		if(score % 2 != 0)
			printf("Collection #%d:\nCan't be divided.\n\n", ++record);
		else{
			score /= 2;
			memset(value, 0, sizeof(value));
			value[0] = 1;
			for(i = 1; i <= 6; ++i){
				for(j = 1; j <= num[i]; ++j)
					for(k = score; k >= i; --k)
						value[k] = (value[k] || value[k - i]);
			}
			if(value[score])
				printf("Collection #%d:\nCan be divided.\n\n", ++record);
			else
				printf("Collection #%d:\nCan't be divided.\n\n", ++record);
		}
		score = 0;
		for(i = 1; i <= 6; ++i){
			scanf("%d", num + i);
			score += i * num[i];
		}
	}
	return 0;
}

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