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

一发TLE之后,加了个预处理,1750ms擦边AC,留下源码~~~

Posted by vjubge4 at 2019-05-30 19:58:36 on Problem 1185
#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:
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