题目链接

思路:

  • 这道题一开始想的状态是$f(i,j)$表示第i个位置放与不放炸弹(用j表示),后来怎么也写不对代码:sweat:,所以我看了眼题解,少了一维。
  • 咳咳,正解:
  • 先设计状态,$f(i,j,k)$表示第i个位置放不放炸弹和下一位放不放炸弹(分别用j,k表示),这样就可以推出转移的方法。
    1. 当第i位数字为0时,那直接从$f(i-1,0,0)$转移过来。
    2. 当为1时,就有分别把炸弹放到3个格子当中的3种方法。
    3. 当为2,3时,同理。

P.S. 题解上说答案只能是大于0,小于2,貌似是的,但是为什么?求大佬解释qwq。

代码如下:

    #include<bits/stdc++.h>
    using namespace std;
    int f[10009][2][2],a[10009],n;
    int main(){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        f[0][0][0]=f[0][0][1]=1;//第0个位置一定不选,下个位置有选和不选两种情况。 
        for(int i=1;i<=n;i++){
            if(a[i]==0)//如果这个位置为0,那这个位置和上下位置均不选。 
                f[i][0][0]+=f[i-1][0][0];
            if(a[i]==1)//如果为1,那可以这个位置和上下两个位置任意一个选。下方同理。 
                f[i][1][0]+=f[i-1][0][1],f[i][0][1]+=f[i-1][0][0],f[i][0][0]+=f[i-1][1][0];
            if(a[i]==2)
                f[i][1][0]+=f[i-1][1][1],f[i][0][1]+=f[i-1][1][0],f[i][1][1]+=f[i-1][0][1];
            if(a[i]==3)
                f[i][1][1]+=f[i-1][1][1];
        }
        cout<<f[n][1][0]+f[n][0][0];//在第n个选与不选的结果相加即为ans。 
        return 0;
    }
Last modification:March 14th, 2020 at 08:49 pm