代码

[SCOI2005]P2327:扫雷

https://www.luogu.org/problem/show?pid=2327

做法:

dp.dp[i][j]表示到第i位的附近三格,有几种形状为j的可能

“形状为j”是什么意思呢,注意到如果附近三格有无雷用0,1表示的话,其实就组成了二进制数字,把他们转化为十进制即为j

那么j最大是7

转移的话直接根据上一次结果和当前数字判断即可,我用了滚动数组

O(n)

#include<cstdio>
#include<cstring>
#define MAXN 10010
using namespace std;
int dp[2][8];
int a[MAXN];
int n, ans = 0;
int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
    	scanf("%d", &a[i]);
    	if (a[i] > 3) {
    		printf("0");
    		return 0;
    	}
    }
    if (a[n] == 3){
    	printf("0");
    	return 0;
    }
    if (n == 1){
        if (a[1] == 1) printf("1");
        else printf("0");
        return 0;
    }
    memset(dp, 0, sizeof(dp));
    if (a[1] == 0) dp[0][0] = 1;
    if (a[1] == 1) dp[0][2] = 1, dp[0][1] = 1;
    if (a[1] == 2) dp[0][3] = 1;
    for (int i = 2; i <= n; i++){
        int w = i & 1;
        int v = (i - 1) & 1;
        memset(dp[v], 0, sizeof(dp[v]));
        if (a[i] == 0){//查看前面以0结尾的数
            dp[v][0] += dp[w][4];
            dp[v][0] += dp[w][0];
        }
        if (a[i] == 1) {
        	if (i != n) dp[v][1] += dp[w][0] + dp[w][4];
        	dp[v][4] += dp[w][2] + dp[w][6];
            dp[v][2] += dp[w][1] + dp[w][5];
        }
        if (a[i] == 2) {
        	if (i != n) dp[v][5] += dp[w][2] + dp[w][6];
            dp[v][3] += dp[w][1] + dp[w][5];
            dp[v][6] += dp[w][3] + dp[w][7];
        }
        if (a[i] == 3) {
            dp[v][7] += dp[w][3] + dp[w][7];
        }
    }

    for (int i = 0; i < 8; i++){
        ans += dp[(n - 1) & 1][i];
    }
    printf("%d", ans);
}

 

b-a
我还没有学会写个人说明!
查看“b-a”的所有文章 →

Leave a Reply

Your email address will not be published. Required fields are marked *

相关推荐