C++14(g++5.4) 解法, 执行用时: 1939ms, 内存消耗: 4216K, 提交时间: 2019-10-05 14:34:41

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=22;
const int maxm=502;
const int mod=1e9+7;
int dp[2][maxm][maxm],a[maxn],b[maxm],c[maxm];
inline void add(int &x,const int &y)
{
    x+=y;
    if(x>=mod) x-=mod;
}
struct BIT
{
    int C[maxm],n;
    inline void init(int _n){
        n=_n;
        memset(C,0,sizeof(int)*(n+1));
    }
    inline void Add(int x,int val){
        while(x<=n){
            add(C[x],val);
            x+=x&-x;
        }
    }
    inline int Sum(int x){
        int ans=0;
        while(x){
            add(ans,C[x]);
            x-=x&-x;
        }
        return ans;
    }
}bit[2][maxm];
int main()
{
    #ifdef local
    freopen("a.in","r",stdin);
    #endif // local
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        for(int i=0;i<n;++i) scanf("%d",a+i);
        for(int i=0;i<m;++i) scanf("%d",b+i),c[i]=b[i];
        sort(c,c+m);
        for(int i=0;i<m;++i) b[i]=lower_bound(c,c+m,b[i])-c+1;
        memset(dp[0],0,sizeof(dp[0]));
        int t=0;
        for(int i=0;i<m;++i) dp[0][i][b[i]]=1;
        for(int i=n-2;i>=0;--i){
            t^=1;
            for(int x=1;x<=m;++x){
                bit[0][x].init(m);
                bit[1][x].init(m);
                dp[t][m-1][x]=0;
            }
            for(int j=m-2;j>=0;--j){
                for(int x=1;x<=m;++x){
                    bit[0][b[j+1]].Add(x,dp[t^1][j+1][x]);
                    bit[1][x].Add(b[j+1],dp[t^1][j+1][x]);
                }
                for(int x=1;x<=m;++x){
                    if(a[i]){
                        if(x<b[j]) dp[t][j][x]=bit[a[i+1]][x].Sum(b[j]-1);
                        else dp[t][j][x]=0;
                    }
                    else{
                        if(x>b[j]) dp[t][j][x]=(bit[a[i+1]^1][x].Sum(m)-bit[a[i+1]^1][x].Sum(b[j])+mod)%mod;
                        else dp[t][j][x]=0;
                    }
                }
            }
        }
        int ans=0;
        for(int i=0;i<m;++i){
            for(int x=1;x<=m;++x){
                add(ans,dp[t][i][x]);
            }
        }
        /*for(int i=n-1;i>=0;--i){
            for(int j=m-1;j>=0;--j){
                for(int k=1;k<=m;++k){
                    cout<<i<<' '<<j<<' '<<k<<' '<<dp[i][j][k]<<endl;
                }
            }
        }*/
        printf("%d\n",ans);
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 3027ms, 内存消耗: 26852K, 提交时间: 2019-10-04 15:22:38

#include <bits/stdc++.h>
using namespace std;
#define rep(i,s,t) for(int i=s;i<t;i++)
#define pii pair<int,int>
typedef long long ll;
int dp[22][555][555],a[22],b[555];
const int mod=1e9+7;
void add(int &a,int b)
{
    a+=b;
    if(a>=mod)a-=mod;
}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)==2)
    {
        rep(i,1,n+1)scanf("%d",&a[i]);
        rep(i,1,m+1)scanf("%d",&b[i]);
        memset(dp,0,sizeof(dp));
        reverse(a+1,a+n+1),reverse(b+1,b+m+1);
        dp[0][0][0]=1;
        rep(i,0,n+1)
        rep(j,0,m+1)
        rep(k,0,m+1)
        if(dp[i][j][k])
        {
            int kk=max(j,k)+1;
            rep(nowpos,kk,m+1)
            {
                if (a[i + 1] == 1)
                {
                    if (j != 0 && b[nowpos] < b[j])continue;
                    add(dp[i + 1][nowpos][k==0?nowpos:k], dp[i][j][k]);
                } else
                {
                    if (k != 0 && b[nowpos] > b[k])continue;
                    add(dp[i+1][j==0?nowpos:j][nowpos],dp[i][j][k]);
                }
            }
        }
        int res=0;
        rep(i,1,m+1)rep(j,1,m+1)add(res,dp[n][i][j]);
        printf("%d\n",res);
    }
}