| ||||||||||
| 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 | |||||||||
一发TLE之后,加了个预处理,1750ms擦边AC,留下源码~~~#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int W, H;
bool field[100][10];
int dp[100][1 << 10][1 << 10];
bool VA[100][1 << 10];
bool OK(int a, int N) {
for(int i = 0; i < W; i ++) {
if((a >> i) & 1) {
if(!field[N][i]) {
return false;
}
if(i > 1) {
if((a >> (i - 2)) & 1) {
return false;
}
}
if(i > 0) {
if((a >> (i - 1)) & 1) {
return false;
}
}
if(i < W - 1) {
if((a >> (i + 1)) & 1) {
return false;
}
}
if(i < W - 2) {
if((a >> (i + 2)) & 1) {
return false;
}
}
}
}
return true;
}
int count1(int a) {
int c = 0;
for(int k = 0; k < W; k ++) {
if((a >> k) & 1) {
c ++;
}
}
return c;
}
int main() {
scanf("%d %d", &H, &W);
for(int i = 0; i < H; i ++) {
getchar();
for(int j = 0; j < W; j ++) {
char t = getchar();
if(t == 'P') {
field[i][j] = true;
}
}
}
if(H == 0 || W == 0) {
printf("0\n");
return 0;
}
for(int i = 0; i < H; i ++){
for(int j = 0; j < (1 << W); j++){
if(OK(j, i)){
VA[i][j] = true;
}
}
}
int ans = 0;
for(int i = 0; i < (1 << W); i ++) {
if(VA[0][i]) {
int c = count1(i);
fill(dp[0][i], dp[0][i] + (1 << W), c);
ans = max(ans, c);
}
}
for(int i = 1; i < H; i ++) {
for(int j = 0; j < (1 << W); j ++) {
if(VA[i][j]) {
int c = count1(j);
for(int u = 0; u < (1 << W); u ++) {
if(VA[i - 1][u] && (u & j) == 0) {
for(int v = 0; v < (1 << W); v ++) {
if((VA[i - 2][v] || i == 1) && (v & j) == 0 && (v & u) == 0) {
dp[i][j][u] = max(dp[i][j][u], dp[i - 1][u][v] + c);
ans = max(ans, dp[i][j][u]);
}
}
}
}
}
}
}
printf("%d\n", ans);
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator