很简单的状态压缩DP。。由于每个格子只管辖左侧3个格子的情况。。所以我们可以直接用一个0-7的整数表示每个格子管辖格子的状态p。。

然后DP方程就是：f[i][p]=f[4 | (p>>1)]+f[p>>1]。。意义是最基本的组合数加法原理。。

递推，没什么可说的，第一次没考虑到n=2的特殊情况，90分。。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

最WS但最容易理解的方程：

var

n,i,j,k1,k2,k3:longint;

a:array[0..10000] of longint;

f:array[0..10000,0..1,0..1,0..1] of longint;

begin

readln(n);

for i := 1 to n do read(a[i]);

readln;

fillchar(f,sizeof(f),0);

f[0,0,0,0] := 1;

f[0,0,0,1] := 1;

f[1,0,0,0] := 1;

f[1,0,0,1] := 1;

f[1,0,1,0] := 1;

f[1,0,1,1] := 1;

for i := 2 to n do

for k1 := 0 to 1 do

for k2 := 0 to 1 do

for k3 := 0 to 1 do

for j := 0 to 1 do

if (k1+k2+k3 = a[i]) and (j+k1+k2 = a) then

f := f+f;

i := 0;

for k1 := 0 to 1 do

for k2 := 0 to 1 do

if (k1+k2 = a[n]) then

i := i+f[n,k1,k2,0];

writeln(i);

end.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

var

f:array[0..10000,0..1,0..1]of longint;

a:array[1..10000]of integer;

n,i,j,k1,k2,k3:longint;

begin

readln(n);

for i:=1 to n do read(a[i]);

fillchar(f,sizeof(f),0);

f[0,0,0]:=1;f[0,0,1]:=1;

for i:=1 to n do

for k1:=0 to 1 do

for k2:=0 to 1 do

for k3:=0 to 1 do

if (k1+k2+k3)=a[i] then inc(f,f);

write(f[n,1,0]+f[n,0,0]);

end.

一个小DP，程序很短，不过方程不是很好想。

由于第i行和第i+1行有关系，所以仅存第i行状态是不够的

要用三维数组把第i+1行状态也存起来

f 表示第i行左边放k2个雷

第i+1行放k3个雷 的方案数。

最后一个为0的情况竟然没考虑。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

simple dp...

f[n,0..1,0..1] is just OK.

裸搜都能秒杀的水题

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

program ex;

var i,j,n,t:longint;

a:array[1..10000]of longint;

f:array[0..10000,0..1,0..1]of longint;

procedure dp;

var i,j1,j2,j3:longint;

begin

f[0,0,0]:=1;

f[0,0,1]:=1;

for i:=1 to n do

for j1:=0 to 1 do

for j2:=0 to 1 do

for j3:=0 to 1 do

if (not((i=1)and(j1=1)))and(not((i=n)and(j3=1)))and(j1+j2+j3=a[i]) then

inc(f,f);

end;

begin

readln(n);

for i:=1 to n do read(a[i]);

dp;

writeln(f[n,0,0]+f[n,1,0]);

end.

f 表示第i行的左边为j1,第i+1行的左边为j2的情况数, j1,j2=1,0表示有无雷

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

计算方法同LX,时间复杂度仅是O(n),貌似比多进程DP感觉好些.

调用函数的方式提高了程序可读性.

虽然忘记考虑a[1]=0的情况wa了一次,总体感觉良好.

#include

#include

int n;

int a[10001];

int ans=0;

int work(int x,int y)

{

int i;

int f[10001];

f[1]=x;

f[2]=y;

for(i=3;i1)break;

}

if(a[n]==f[n]+f[n-1] && i==n+1)return 1;

else return 0;

}

int main()

{

scanf("%d",&n);

int i;

for(i=1;i

由前两格就可以推出下一格

a[i]:第i格的周围的雷数

b[i]:第i格的雷数(只能是0或1)

则有

b+b[i]+b=a[i]

所以

b=a[i]-b[i]-b

如果b不是0或着1那么无解.

因此只要枚举前两个点的状态就可以了.

答案也就不超过2种

PS:第二个数据的第一位居然是0,在这里死了N次

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

-,-?动规？

用递推过了9个点。。

画几次就可以发现只有0、1、2三种情况。。

打算此题Cheat的飘过- -|||

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：运行超时...

├ 测试数据 07：运行超时...

├ 测试数据 08：运行超时...

├ 测试数据 09：运行超时...

├ 测试数据 10：运行超时...

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：50 有效耗时：0ms

我用的是搜索，为什么

编译通过...

├ 测试数据 01：答案错误...　├ 标准行输出 0

　├ 错误行输出 1

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：90 有效耗时：0ms

#include

#include

#include

long D[3][4],N;

int main(void){

long i,j,x;

scanf("%ld%ld",&N,&x);

if (N==1){

if (x==0) printf("1\n");else

if (x==1) printf("1\n");else

printf("0\n");

return 0;

}

if (x==0) D[1][0]=1;

if (x==1) D[1][1]=D[1][2]=1;

if (x==2) D[1][3]=1;

for (i=2;i

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

//By F.u

var

data:array[1..10000] of longint;

f:array[0..10000,0..1] of integer;

i,j,k,n,p:longint;

begin

readln(n);

for i:=1 to n do read(data[i]);

f[1,0]:=1; f[0,0]:=1;

if data[1]0 then begin f[1,1]:=1; end;

for i:=2 to n do

for j:=0 to 1 do

for k:=0 to 1 do

begin

p:=data-j-k;

if ((p=1) or (p=0)) and (f0) and (f0)

then

begin

inc(f);

if i=n then

if p+kdata[n] then dec(f);

end;

end;

writeln(f[n,0]+f[n,1]);

end.

1次AC

#include

int a[10001],n,f[10001][2][2][2];

int main()

{

scanf("%d",&n);

int i,j,k,m,l;

for(i=1;i

var i,j,k,l,m,n:longint;

f:array[1..20000,0..1,0..1,0..1]of longint;

a:array[1..20000]of longint;

begin

readln(n);

for i:=1 to n do read(a[i]);

for i:=0 to 1 do

for j:=0 to 1 do

if i+j=a[1] then f[1,i,j,0]:=1;

for i:=2 to n do

for j:=0 to 1 do

for k:=0 to 1 do

for l:=0 to 1 do

for m:=0 to 1 do

begin

if j+k+l=a[i] then

f:=f+f;

end;

writeln(f[n,0,1,0]+f[n,0,1,1]+f[n,0,0,1]+f[n,0,0,0]);

end.

首次一测就AC！！！ 撒花+鸣礼炮！！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

***|\**|\**|\**|\**|\**|\**|\**|\**|\**|\**|\**|\**|\*|

var n,i,j,k,sum:integer;

a:array[0..10000]of integer;

f:array[0..10000,-3..3,-3..3]of longint;

begin

read(n);

for i:=1 to n do

begin

read(a[i]);

if (i=1)or(i=n) then

if a[i]=3 then begin write(0); halt; end;

if (a[i]+a=4)and(a[i]a) then

begin write(0); halt; end;

end;

f[1,0,0]:=1; f[1,1,1]:=1;

for i:=2 to n+1 do

for j:=0 to 1 do

for k:=0 to 2 do

f:=f[i-1,k-j,a-j];

sum:=f[n+1,0,0]+f[n+1,0,1];

write(sum);

end.

不要想得太简单，也不要想得太复杂。

大胆一点，把状态全部表示出来，思路就清晰了。

f[t][i][j][k]表示前格,且t-1格的状态为i,t格的状态为j,t+1格的状态为k的方案数.

0

这个..如果用状态压缩DP的话就不容易把那些一开始就已经确定的位置计算进来了吧..

有什么办法可以也实现这点么...