超算居然有oj了！，我一定要占领制高地

首先，如果你是法国赌神皮尔卡松,那么请提交这段代码。

#include<bits/stdc+++.h>
using namespace std;
int main()
{
    srand(static_cast<unsigned int>(time(0)));
    int random_num=rand()%3;
    cout<<random_num<<endl;
    return 0;
}

我只得了40

好了，言归正传，我们使用三维dp,将dp[i][a][b]表示在第i个位置上当前位置是不是雷(用j表示),下一位置需不需要是雷(k)的方案数。

using namespace std;
int dp[10009][2][2];
int main()
{
    int n;
    cin>>n;
    dp[0][0][1]=1;
    dp[0][0][0]=1;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        if(x==0)
        {
            dp[i][0][0]+=dp[i-1][0][0];
        }
        if(x==1)
        {
            dp[i][0][0]+=dp[i-1][1][0];
            dp[i][1][0]+=dp[i-1][0][1];
            dp[i][0][1]+=dp[i-1][0][0];
        }
        if(x==2)
        {
            dp[i][0][1]+=dp[i-1][1][0];
            dp[i][1][0]+=dp[i-1][1][1];
            dp[i][1][1]+=dp[i-1][0][1];
        }
        if(x==3)
        {
            dp[i][1][1]+=dp[i-1][1][1];
        }
    }
    cout<<dp[n][0][0]+dp[n][1][0];
    return 0;
}

但是看看法国赌神专用代码！！

其实只要第一个点确定了；后面全都确定了

所以只要令b[1]=1扫一遍；再令b[1]=0扫一遍,所以答案只可能是0 1 2 !!!!

#include<bits/stdc++.h>
using namespace std;
int i,j,k,m,n,ans=2,a[10001],b[10001];
void checkx()
{
    for(int i=2;i<=n+1;i++)
    {
    b[i]=a[i-1]-b[i-1]-b[i-2];
    if (!(b[i]==1||b[i]==0))
          {
          ans--;
          break;
          }
          if (i==n+1&&b[i]!=0)
                {
                 ans--;
                 break;
             }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    b[0]=0;
    for (i=1;i<=n;i++)    
    cin>>a[i];
    b[1]=1;
    checkx();
    b[1]=0;
     checkx();
    cout<<ans;   
return 0;    
}

觉得好就在评论区夸人家两句吧,人家可是在比赛上A了的

1

1