100 Unaccepted 求助
查看原帖
100 Unaccepted 求助
547908
NightTide楼主2022/4/4 16:30

官方数据全部过掉了,但是民间数据一塌糊涂,错得没剩下几个

这是记录:https://www.luogu.com.cn/record/73152552

把代码贴在这里,求大神帮我看看

#include<bits/stdc++.h>
#define MAXN 410
#define MOD (ll)(1e9+7)
using namespace std;
typedef long long ll;
int n,m,cas;
string s,r,t;
namespace accepted{
    ll f[2][MAXN][MAXN],sum[MAXN];
    void main(){
        for(int i=1;i<=n;i++) sum[i] = sum[i-1] + (s[i] == '-');
        f[0][0][0] = 1;
        for(int i=0;i<n;i++){
            memset(f[(i+1) & 1],0,sizeof(f[(i+1) & 1]));
            // for(int j=0;j<m && j<i;j++){
                for(int k=0;i - k - sum[i] * 2 >= 0;k++){
                    //     int l = i - sum[i] - k - j;
                    //     if(s[i] == '-'){
                    //         if(k) f[(i+1) & 1][j][k-1] += f[i & 1][j][k];
                    //         if(l) f[(i+1) & 1][j][k]   += f[i & 1][j][k];
                    //     }else{
                    //         f[(i+1) & 1][j][k] += f[i & 1][j][k];
                    //         if(j == 0 && l == 0) f[(i+1) & 1][j][k+1] += f[i & 1][j][k];
                    //         if(s[i] == t[j+1] && l == 0){
                    //             f[(i+1) & 1][j+1][k] += f[i & 1][j][k];
                    //         }
                    //     }
                    // }
                    for(int l=0;i - k - l - sum[i] * 2 >= 0;l++){
                        int j = i - k - l - sum[i] * 2;
                        if(s[i+1] == '-'){
                            if(k) f[(i+1) & 1][k-1][l] += f[i & 1][k][l], f[(i+1) & 1][k-1][l] %= MOD; // 删去开头的数字
                            if(l) f[(i+1) & 1][k][l-1] += f[i & 1][k][l], f[(i+1) & 1][k][l-1] %= MOD; // 删去末尾的数字
                        }else{
                            f[(i+1) & 1][k][l+1] += f[i & 1][k][l]; // 加入末尾的数字不需要
                            if(j == 0 && l == 0) f[(i+1) & 1][k+1][l] += f[i & 1][k][l], f[(i+1) & 1][k+1][l] %= MOD;
                            if(s[i+1] == t[j+1] && l==0){
                                f[(i+1) & 1][k][l] += f[i & 1][k][l];
                                f[(i+1) & 1][k][l] %= MOD;
                            }
                        }
                        // printf("i = %d j = %d k = %d l = %d f = %lld\n",i,j,k,l,f[i & 1][k][l]);
                    }
                }
            // }
        }
        printf("%lld\n",f[n & 1][0][0]);
    }
}
string read(){
    char c; string tmp;
    while(!(isdigit(c) || c=='-')) c=getchar();
    while(isdigit(c) || c=='-'){
        tmp+=c; c=getchar();
    }
    return tmp;
}
int main(){
    scanf("%d",&cas);
    while(cas--){
        s.clear(); t.clear();
        scanf("%d%d",&n,&m);
        s += ' '; t += ' ';
        s+=read(); t+=read();
        // single_dfs::main();
        accepted::main();
    }
    return 0;
}
2022/4/4 16:30
加载中...