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
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

dp,水

Posted by KatrineYang at 2016-09-09 12:30:24 on Problem 1321
#include <iostream>
#include <stdio.h>
using namespace std;

int numOf1[256];

void preprocess(){
	for(int n = 0; n < 256; n++){
		int cnt = 0;
		for(int i = 0; i < 8; i++){
			if((n & (1 << i)) != 0) cnt++;
		}
		numOf1[n] = cnt;
	}
}

int main() {
	preprocess();
	while(1){
		int n,k;
		scanf("%d%d", &n, &k);
		if(n == -1 && k == -1) break;
		bool has[10][10] = {0};
		for(int i = 1; i <= n; i++){
			char rubbish[10];
			scanf("%s", rubbish);
			for(int j = 0; j < n; j++){
				if(rubbish[j] == '#') has[i][j] = 1;
			}
		}

		long long int dp[10][257];
		dp[0][0] = 1;
		int zd = (1 << n);
		for(int i = 1; i < zd; i++) dp[0][i] = 0;
		for(int i = 1; i <= n; i++){
			for(int st = 0; st < zd; st++){
				if(numOf1[st] > i) dp[i][st] = 0;
				else{
					long long int res = dp[i-1][st];
					for(int pos = 0; pos < n; pos++){
						if(has[i][pos] && (st & (1 << pos)) != 0){
							res += dp[i-1][st-(1<<pos)];
						}
					}
					dp[i][st] = res;
				}
			}
		}
		long long int ans = 0;
		for(int st = 0; st < zd; st++){
			if(numOf1[st] != k) continue;
			ans += dp[n][st];
		}
		printf("%I64d\n", ans);
	}
	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