BZOJ1088(SCOI2005)

枚举第一行第一个格子的状态(有雷或者无雷，0或1),然后根据第一个格子推出后面所有格子的状态。推出之后判断解是否可行即可。

#include <bits/stdc++.h>

using namespace std;

#define REP(i,n)                for(int i(0); i <  (n); ++i)

#define rep(i,a,b)              for(int i(a); i <= (b); ++i)

#define dec(i,a,b)              for(int i(a); i >= (b); --i)

#define for_edge(i,x)           for(int i = H[x]; i; i = X[i])

#define LL      long long

#define ULL     unsigned long long

#define MP      make_pair

#define PB      push_back

#define FI      first

#define SE      second

#define INF     1 << 30

const int N     =    100000      +       10;

const int M     =    10000       +       10;

const int Q     =    1000        +       10;

const int A     =    30          +       1;

int a[N], b[N];

int n;

int ans;

int main(){

#ifndef ONLINE_JUDGE

	freopen("test.txt", "r", stdin);

	freopen("test.out", "w", stdout);

#endif

	scanf("%d", &n);

	rep(i, 1, n) scanf("%d", a + i);

	rep(i, 0, 1){

		bool flag = true;

		b[1] = i;

		rep(j, 2, n) b[j] = a[j - 1] - b[j - 1] - b[j - 2];

		rep(j, 2, n - 1) if (b[j] < 0 || b[j] > 1){ flag = false; break;}

		if (b[n] < 0 || b[n] > 1) flag = false;

		rep(j, 1, n) if (b[j - 1] + b[j] + b[j + 1] != a[j]){ flag = false; break;}

		//rep(j, 1, n) printf("%d ", b[j]); putchar(10);

		if (flag) ++ans;

	}

	printf("%d\n", ans);

	return 0;

}

巴特西

BZOJ1088(SCOI2005)

最新文章

热门文章