[SCOI2005]扫雷MINE

题目链接:https://ac.nowcoder.com/acm/problem/20241

这个题是可以用dp写的(虽然我dp贼菜,写这玩意写的我头大)。不过这个题还是蛮好懂的(看了大佬题解以后)。

每个位置只有有雷或者没雷两种情况,我们可以用0表示没有雷,1表示有雷。我们用x数组来存数量,y数组来存当前位置有没有雷,根据扫雷的规则,我们可以得到,x[i]=y[i-1]+y[i]+y[i+1],转换一下可以得到y[i+1]=x[i]-y[i]-y[i-1]。因此我们就得到了状态转移方程,我们就可以用它来解题啦。具体看代码注释。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int x[100005]={0};
int y[100005]={0};
int ans=0;
int n;
int solve()
{
    for(int i=2;i<n;i++)
    {
        y[i+1]=x[i]-y[i]-y[i-1];
        if(y[i+1]<0||y[i+1]>1) return 0;//当前位置只能为0或者为1哦 
    }
    if(y[n]+y[n-1]!=x[n]) return 0;//最后一个位置判断一下 
    return 1;
}
int main()
{
    cin>>n;
    int flag=0;
    for(int i=1;i<=n;i++)
    {
        cin>>x[i];
        if(x[i]>3) flag=1;//大于三个当然不可能啦 
    }
    if(x[1]>2||x[n]>2||flag==1)//第一个和最后一个最多只能有两个啦 
    {
        cout<<0;
        return 0;
    }
    if(x[1]==2)//第一个和第二个位置都有雷 然后解题 
    {
        y[1]=1;
        y[2]=1;
        ans+=solve();
    }
    else if(x[1]==0)//第一个和第二个位置没有雷 
    {
        y[1]=0;
        y[2]=0;
        ans+=solve();
    }
    else if(x[1]==1)//有两种情况,搞一下就可以了 
    {
        y[1]=1;
        ans+=solve();
        memset(y,0,sizeof(y));
        y[2]=1;
        ans+=solve();
    }
    cout<<ans;//完事 
}
全部评论

相关推荐

关于我大学本科四年,想了很多,但还是不知道该怎么动笔&nbsp;“大学四年,是我从懵懂少年走向职场青年的转折期。这一路跌跌撞撞,有迷茫,有遗憾,也有成长和决心。”&nbsp;大一刚进来时仍然有高中那股学习劲,经常一个人去图书馆学高等数学,但后面劲头一过便开始在宿舍开启躺平生活(现在想想那段时间真的很爽,无忧无虑)。由于大一担任班干部,所以经常要跟其他班的班干部交流,在此期间认识了隔壁班的一位女生,短发而很可爱,因为很多团建还有比赛都是我们两班一起参加的,而且我和她都是负责人,所以交集很多,后面慢慢地彼此对产生了好感,所以在大一刚开学的2个月后,我们在一起了,彼此之前都是初恋。但当时我真的是太太太直男了,对感情的想...
真烦好烦真烦:骗哥们可以,别把你自己也骗到了就行。哥们被你骗了真无所谓的,打个哈哈就过了。但希望你打完这段话后擦一下眼角,别让眼泪掉在手机屏幕上了就行。你说的这些话,哥们信一下也是没什么的。还能让你有个心里安慰,但这种话说出来骗骗兄弟就差不多得了,哥们信你一下也不会少块肉,但是你别搞得自己也当真了就行。哥们被你骗一下是真无所谓的,兄弟笑笑也就过去了。真不是哥们想要破你防,你擦擦眼泪好好想想,除了兄弟谁还会信你这些话?
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务