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

大水题

Posted by KatrineYang at 2016-09-08 10:19:43 on Problem 1285
#include <iostream>
#include <stdio.h>
using namespace std;

int mx(int a, int b){
	return (a>b) ? a : b;
}

int main() {
	int T = 0;
	while(1){
		int n,m;
		scanf("%d%d", &n, &m);
		if(n == 0 && m == 0) break;
		T++;
		int sta[55] = {0};
		for(int i = 0; i < n; i++){
			int temp;
			scanf("%d", &temp);
			sta[temp] ++;
		}
		int cnt = 0;
		int gs[55] = {0};
		for(int i = 0; i < 55; i++){
			if(sta[i] > 0){
				cnt++;
				gs[cnt] = sta[i];

			}
		}
		int bfh[55];
		bfh[0] = 0;
		for(int i = 1; i <= cnt; i++){
			bfh[i] = bfh[i-1] + gs[i];
		}
		long long int dp[55][55] = {0};
		dp[0][0] = 1;
		for(int i = 1; i <= cnt; i++){
			for(int j = 0; j <= bfh[i]; j++){
				long long int ans = 0;
				for(int k = mx(0, j-bfh[i-1]); k <= gs[i] && k <= j; k++){
					ans += dp[i-1][j-k];
				}
				dp[i][j] = ans;
			}
		}
		printf("Case %d:\n", T);
		for(int i = 0; i < m; i++){
			int temp;
			scanf("%d", &temp);
			printf("%I64d\n", dp[cnt][temp]);
		}
	}
	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