QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#760350#3040. ContainerczcWA 0ms9548kbC++232.8kb2024-11-18 16:25:272024-11-18 16:25:27

Judging History

你现在查看的是最新测评结果

  • [2024-11-18 16:25:27]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:9548kb
  • [2024-11-18 16:25:27]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;  
int C,n,c;
char a[maxn],b[maxn];
vector<int> pos1,pos2[maxn];
int f[maxn][maxn],pre[maxn][maxn];
inline int g(int d){
    return (d/2)*(c+4)+(d%2)*(c+3);
}
int sum[2][maxn][maxn];
int main(){
    scanf("%d%d%d",&C,&n,&c);
    scanf("%s",a+1);
    scanf("%s",b+1);
    for(int i=1;i<=n;i++){
        if(a[i]=='B') pos1.push_back(i);
        if(b[i]=='B'){
            pos2[i%2].push_back(i);
        }
    }
    for(int op=0;op<2;op++){
        for(int i=0;i<pos2[op].size();i++){
            for(int j=1;j<=n;j++){
                if(i) sum[op][i][j]=sum[op][i-1][j];
                sum[op][i][j]+=(pos2[op][i]>j);
            }
        }
    }
    memset(f,0x3f,sizeof(f));
    f[0][0]=0;
    for(int i=1;i<=(int)pos1.size();i++){
        for(int j=0;j<=min((int)pos2[1].size(),i-1);j++){
            if(f[i-1][j]==0x3f3f3f3f) continue;
            if(j<pos2[1].size()){
                //f i-1,j -> f i,j+1  match pos2[1][j] pos[i-1] 
                int s=g(abs(pos2[1][j]-pos1[i-1]));
                int dl=(i-j-1)?sum[0][i-j-2][pos2[1][j]]:0;
                if(f[i][j+1]>f[i-1][j]+s+dl){
                    f[i][j+1]=f[i-1][j]+s+dl;
                    pre[i][j+1]=1;
                }
            }
            if(i-1-j<pos2[0].size()){
                //f i-1,j -> f i,j    match pos2[0][i-j-1] pos[i-1]
                int s=g(abs(pos2[0][i-j-1]-pos1[i-1]));
                int dl=j?sum[1][j-1][pos2[0][i-j-1]]:0;
                if(f[i][j]>f[i-1][j]+s+dl){
                    f[i][j]=f[i-1][j]+s+dl;
                    pre[i][j]=0;
                }
            }
        }
    }
    int m=pos1.size(),odd=pos2[1].size(),even=pos2[0].size();
    vector< pair<int,int> > a[2];
    while(m){
        int pr=pre[m][odd];
        if(pr==1){
            m--,odd--;
            int st=pos1[m],en=pos2[1][odd];
            if(st<en) a[0].push_back({st,en});
            else a[1].push_back({st,en});
        }
        else{
            m--,even--;
            int st=pos1[m],en=pos2[0][even];
            if(st<en) a[0].push_back({st,en});
            else a[1].push_back({st,en});
        }
    }
    vector< pair<int,int> > ans;
    for(auto y:a[0]){
        int st=y.first,en=y.second;
        while(st+2<=en){
            ans.push_back({st,st+2});
            st+=2;
        }
        if(st!=en) ans.push_back({st,en});
    }
    reverse(a[1].begin(),a[1].end());
    for(auto y:a[1]){
        int st=y.first,en=y.second;
        while(st-2>=en){
            ans.push_back({st-2,st});
            st-=2;
        }
        if(st!=en) ans.push_back({en,st});
    }
    printf("%d\n",(int)ans.size());
    for(auto x:ans) printf("%d %d\n",x.first,x.second);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 9548kb

input:

5 2
11221
21112

output:

0

result:

wrong answer invalid plan.