星星灰暗着。

星星灰暗着。

你所见的的确是一个NOIp退役OIer的博客。

P2327 [SCOI2005] 扫雷

posted on 2017-12-10 15:16:49 | under 题解 |

曾经的lofterOI一血。

虽然这是在模拟复习课上讲的题,但我的第一反应果然还是DFS233333

最初的暴力想法是,在每个点上搜索,枚举相邻点是否有雷,O(2^n),这样估摸着能得30分。

然后某位大佬光速回答:用DP然后把我们其他人都怒虐了一遍,不得不叹服dalao。

可以看出,当我们知道f[i],f[i-1],a[i]的时候,f[i+1]是直接可以算出来的。

f[i]代表1行i列的雷数量,枚举f[1]=0或1的情况,f[i+1]=a[i]-f[i]-f[i-1],当f[i+1]大于1或小于0时直接Break,最后判断f[n+1]是否有雷,如果无雷代表合法。

所以最后的答案只有012三种。

【有人专门测试过输出012的得分

代码量十分小,貌似洛谷有相似题解。

#include<cstdio>
#define f(i,a,b) for(i=a;i<=b;++i)
int flag,n,a[10010],f[10010];
int main()
{
//    freopen("minesweeper.in","r",stdin);
//    freopen("minesweeper.out","w",stdout);
    int i,j;
    scanf("%d",&n);
    f(i,1,n)scanf("%d",&a[i]);
    f[1]=0;
    f(i,1,n)
    {f[i+1]=a[i]-f[i]-f[i-1];if(f[i+1]>1||f[i+1]<0)break;}
    if(i==n+1&&f[i]==0)++flag;
    f[1]=1;
    f(i,1,n)
    {f[i+1]=a[i]-f[i]-f[i-1];if(f[i+1]>1||f[i+1]<0)break;}
    if(i==n+1&&f[i]==0)++flag;
    printf("%d\n",flag);
}

曾经写下的“876*292的白色你满意了吧”