本题AC AT上WA求助
查看原帖
本题AC AT上WA求助
578029
ivyjiao楼主2024/9/15 16:25

rt,另外如果有人知道 ahck 原理的话,能不能@管理在本题加一组hack?

#include<bits/stdc++.h>
using namespace std;
const int N=401;
int n,dp[2][N][N][3],a[N][3],sum[N][3],l1,l2,l3;
char s[N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        if(s[i]=='R') a[++l1][0]=i;
        if(s[i]=='G') a[++l2][1]=i;
        if(s[i]=='Y') a[++l3][2]=i;
        sum[i][0]=sum[i-1][0]+(s[i]=='R');
        sum[i][1]=sum[i-1][1]+(s[i]=='G');
        sum[i][2]=sum[i-1][2]+(s[i]=='Y');
    }
    if(max({l1,l2,l3})>n/2+1){
        cout<<-1;
        return 0;
    }
    memset(dp,0x3f,sizeof dp);
	dp[1][1][0][0]=a[1][0]-1;
	dp[1][0][1][1]=a[1][1]-1;
	dp[1][0][0][2]=a[1][2]-1;
    for(int i=2;i<=n;i++){
        for(int j=0;j<=l1;j++){
            for(int k=0;k<=l2;k++){
                int l=i-j-k;
                if(l>l3) continue;
                if(j) dp[i%2][j][k][0]=min(dp[(i-1)%2][j-1][k][1],dp[(i-1)%2][j-1][k][2])+a[j][0]+max(0,k-sum[a[j][0]][1])+max(0,l-sum[a[j][0]][2])-i;
                if(k) dp[i%2][j][k][1]=min(dp[(i-1)%2][j][k-1][0],dp[(i-1)%2][j][k-1][2])+a[k][1]+max(0,j-sum[a[k][1]][0])+max(0,l-sum[a[k][1]][2])-i;
                if(l) dp[i%2][j][k][2]=min(dp[(i-1)%2][j][k][0],dp[(i-1)%2][j][k][1])+a[l][2]+max(0,j-sum[a[l][2]][0])+max(0,k-sum[a[l][2]][1])-i;
            }
        }
    }
    cout<<min({dp[n%2][l1][l2][0],dp[n%2][l1][l2][1],dp[n%2][l1][l2][2]});
}
2024/9/15 16:25
加载中...