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

## 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: