题解：P11092 [ROI 2021 Day 2] 莫斯科数字

Erica_N_Contina · 2024-09-29 15:49:03 · 题解

我的博客

更多相关（或者不相关）知识点快戳：oi-beats，个人博客。

知识点摘录

dp。

大意

难度绿。

做法

首先是敲了一下贪心，发现不对，因此考虑 dp。

那么自然是对于每个问号枚举填哪一个了，然后再枚举上一个问号填什么。

定义 f_{i,j} 为第 i 个问号填 j 时，第 i 个问号及以前的字符的总价值的最大值。每次枚举前一个问号的值，把这两个问号之间的价值加上去即可。

有一个性质可以化简算法，就是问号中填的字符一定是单调不升的。

下面是部分实现：

一开始计算后缀最大值，将符合条件的字符的价值置为负。
然后从前往后枚举，遇到问号时执行 dp。注意对于那些没有置为负的字符，有可能因为当前问号而置为负。还要注意当前问号填的字母的价值有可能因为后面的字符而置为负（但是不可能因为后面的问号而置负，见上文性质）。
转移方程 f_{i,j}=\max(f_{i-1,k}+w(pos_{i-1}+1,pos_i))，w(l,r) 计算方法可以自己思考或者参考代码。

// Memory Limit: 256 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>

using namespace std;
#define rd read()
#define ull unsigned long long
#define int long long 
#define itn int
#define ps second 
#define pf first

int read(){
    int x;
    cin>>x;
    return x;
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() {
    cerr << endl;
}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) {
    for (auto v: a) cerr << v << ' ';
    err(x...);
}
template<typename T, typename... A>
void err(T a, A... x) {
    cerr << a << ' ';
    err(x...);
}
#else
#define dbg(...)
#endif
const int N=3e5+5;
const ull P=137;
const int INF=2e18;
/*

策略

贪心还是dp？

*/

int sum[30];
int rsum[30];
string s;
int pw[15];

inline int calVal(char c){
    int t=c-'A';

    // cdbg(c,pw[t/2]*((t&1)?5:1));
    return pw[t/2]*((t&1)?5:1);
}
inline int getDiff(int c){
    int res=calVal(c+'A');
    for(int i=0;i<c;i++){
        res-=2*sum[i];
    }
    return res;
}

int f[N][30];//第i个问号填字母j得到的最大价值

int stk[N];
int top;
int pre[N][30];
int pr[30];
bool r[N];
char suf[N];

void solve(){
    pw[0]=1;
    for(int i=1;i<=13;i++){
        pw[i]=pw[i-1]*10;
    }

    for(int i=0;i<30;i++){
        sum[i]=rsum[i]=0;
    }

    cin>>s;
    int n=s.size();
    s=" "+s;

    for(int i=1;i<=n;i++){
        r[i]=0;
    }

    char mx=0;
    for(int i=n;i;i--){
        suf[i]=mx;
        if(s[i]=='?')continue;
        if(s[i]<mx)r[i]=1;
        mx=max(mx,s[i]);
    }

    int tot=0;

    // // cdbg("OK");
    // memset(f,-0x3f3f,sizeof f);
    for(int i=0;i<26;i++)f[0][i]=0;
    for(int loc=1;loc<=n;loc++){
        if(s[loc]=='?'){
            tot++;
            for(int i=0;i<26;i++){
                f[tot][i]=-INF;
                int del=0;
                for(int i=0;i<26;i++){
                    del+=rsum[i];
                    pr[i+1]=pr[i]+sum[i];
                }

                for(int j=i;j<26;j++){
                    int res=f[tot-1][j]-del;
                    res+=pr[26]-pr[i];
                    if(i>0)res-=pr[i];
                    int val=(suf[loc]>(i+'A')?-1:1)*calVal(i+'A');
                    if(f[tot][i]<res+val)pre[tot][i]=j;//这里取不取等都行，因为有spj
                    f[tot][i]=max(f[tot][i],res+val);
                }
            }
            for(int i=0;i<26;i++)sum[i]=rsum[i]=0;

        }else{
            if(r[loc]){
                rsum[s[loc]-'A']+=calVal(s[loc]);
            }else{
                sum[s[loc]-'A']+=calVal(s[loc]);
            }
            // for(int j=0;j<s[i]-'A';j++){
            //     rsum[j]+=sum[j];
            //     sum[j]=0;
            // }
        }
    }
    {
        int i=0;
        tot++;
        f[tot][i]=-INF;
        for(int j=i;j<26;j++){
            int res=f[tot-1][j];
            for(int k=0;k<26;k++){
                if(k<i)res-=sum[k];
                else res+=sum[k];

                res-=rsum[k];
            }
            if(n<=1000)if(f[tot][i]<res)pre[tot][i]=j;//这里取不取等都行，因为有spj
            f[tot][i]=max(f[tot][i],res);
        }

        for(int i=0;i<26;i++)sum[i]=rsum[i]=0;
    }

    int ans=f[tot][0];
    // for(int i=0;i<26;i++){
    //     ans=max(ans,f[tot][0]);
    // }
    // for(int i=0;i<26;i++){
    //     ans+=sum[i];
    //     ans-=rsum[i];
    // }
    cout<<ans<<endl;
    int cur=tot;
    int bef=0;
    while(cur>1){
        stk[++top]=pre[cur][bef];
        bef=pre[cur--][bef];
    }
    // top=0;
    for(int i=1;i<=n;i++){
        if(s[i]=='?')putchar((char)('A'+stk[top--]));
        else putchar(s[i]);
    }

    puts("");

    // top=0;

    // cout<<s.substr(1)<<endl;
}

signed main(){
    int T=rd;
    while(T--){
        solve();
    }
    return 0;
}