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