2023牛客寒假算法基础集训营6 D（DP）

fried-chicken的的代码

using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define sz(v) ((int)v.size())
#define fs first
#define sc second
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
char s[200010],udu[]="*udu";
int n;
ll dpz[200010][4],dpf[200010][4];
void work(ll dp[][4]){
    dp[0][0]=1;
    rep(i,1,n){
        dp[i][0]=1;
        rep(j,1,3){
            dp[i][j]=dp[i-1][j];
            if(s[i]==udu[j]) dp[i][j]+=dp[i-1][j-1];
        }
    }
}
int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    work(dpz);
    reverse(s+1,s+1+n);
    work(dpf);
    reverse(s+1,s+1+n);
    ll mn=1e18,pos=-1;
    rep(i,1,n){
        ll tmp=0;
        tmp+=dpz[i-1][3]*dpf[n-i][0];
        tmp+=dpz[i-1][2]*dpf[n-i][1];
        tmp+=dpz[i-1][1]*dpf[n-i][2];
        tmp+=dpz[i-1][0]*dpf[n-i][3];
        if(tmp<mn){
            mn=tmp;
            pos=i;
        }
    }
    s[pos]='z';
    puts(s+1);
    return 0;
}