我应该倒计时吗...？

Problem

给出一列数字，需要你添加任意多个逗号将其拆成若干个严格递增的数。如果有多组解，则输出使得最后一个数最小的同时，字典序最大的解（即先要满足最后一个数最小；如果有多组解，则使得第一个数尽量大；如果仍有多组解，则使得第二个数尽量大，依次类推……）。
$n\leq 500$

Solution

正着做一遍 dp，含义为合法的末尾最小的序列

知道了末尾最小值，再反着做一遍 dp，含义为合法的前端最大的序列

大概可以用贪心解释这个 dp...？

字典序最大就是先保证第一个最大，再保证第二个最大

因此具有最优子结构性质，所以可以这样 dp...（口胡）

当然也有更科学的 $O(n^4)$dp，$\text{90pts}$ 不也挺好么逃

Code

// Code by ajcxsu
// Problem: break sequence

#include<bits/stdc++.h>
using namespace std;

const int N=510;

string str;
string bef(string x) {
    int i=0, j=x.size();
    while(i!=j-1 && x[i]=='0') i++;
    return x.substr(i, x.size()-i);
}
int cmp(const string &a, const string &b) {
    string x=bef(a), y=bef(b);
    if(x.size()<y.size()) return -1;
    else if(x.size()>y.size()) return 1;
    else if(x<y) return -1;
    else if(x>y) return 1;
    return 0;
}

int f[N], g[N];

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    memset(f, -1, sizeof(f));
    cin>>str;
    int n=str.size();
    str.insert(str.begin(), ' ');
    for(int i=1;i<=n;i++) {
        f[i]=0;
        for(int j=i-1;j>=1;j--)
            if(cmp(str.substr(f[j]+1, j-f[j]), str.substr(j+1, i-j))<0) {
                f[i]=j;
                break;
            }
    }
    for(int i=f[n]+1;i>=1;i--) {
        if(cmp(str.substr(f[n]+1, n-f[n]), str.substr(i, n-i+1))==0) g[i]=n+1;
        else
            for(int j=f[n]+1;j>i;j--)
                if(cmp(str.substr(j, g[j]-j), str.substr(i, j-i))>0) { g[i]=j; break; }
    }
    int i=1;
    while(g[i]) {
        if(i>1) cout<<',';
        cout<<str.substr(i, g[i]-i), i=g[i];
    }
    cout<<endl;
    return 0;
}

DLC - 90pts

// Code by ajcxsu
// Problem: break sequence

#include<bits/stdc++.h>
using namespace std;

const int N=510;
int f[N][N];

string str;
string bef(string x) {
    int i=0, j=x.size();
    while(i!=j-1 && x[i]=='0') i++;
    return x.substr(i, x.size()-i);
}
int cmp(const string &a, const string &b) {
    string x=bef(a), y=bef(b);
    if(x.size()<y.size()) return -1;
    else if(x.size()>y.size()) return 1;
    else if(x<y) return -1;
    else if(x>y) return 1;
    return 0;
}

vector<string> nans, tob;
void get(int x, int y) {
    tob.clear();
    int tx, ty;
    while(x) {
        tob.push_back(str.substr(x-y+1, y));
        ty=y, y=f[x][y], x-=ty;
    }
    reverse(tob.begin(), tob.end());
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    memset(f, -1, sizeof(f));
    cin>>str;
    int n=str.size();
    str.insert(str.begin(), ' ');
    for(int i=1;i<=n;i++)
    for(int j=1;j<=i;j++) {
        if(i==j) f[i][j]=0;
        nans.clear();
        for(int k=1;k<=i-j;k++)
            if(f[i-j][k]!=-1 && cmp(str.substr(i-j-k+1, k), str.substr(i-j+1, j))<0) {
                get(i-j, k);
                char sm=f[i][j]==-1;
                int l=0, x;
                while(l<nans.size() && l<tob.size()) {
                    if((x=cmp(nans[l], tob[l]))>0) break;
                    else if(x<0) { sm=1; break; }
                    l++;
                }
                if(l==nans.size()) sm=1;
                if(sm) f[i][j]=k, nans.swap(tob);
            }
    }
    nans.clear();
    for(int j=1;j<=n;j++)
        if(f[n][j]!=-1) {
            get(n, j);
            char sm=0;
            int l=0, x;
            while(l<nans.size() && l<tob.size()) {
                if((x=cmp(nans[l], tob[l]))>0) break;
                else if(x<0) { sm=1; break; }
                l++;
            }
            if(l==nans.size()) sm=1;
            if(sm) nans.swap(tob);
            if(j==n || cmp(str.substr(n-j+1, j), str.substr(n-j, j+1))) break;
        }
    for(int i=0, j=nans.size(); i<j; i++)
        cout<<nans[i]<<",\n"[i==j-1];
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-1415.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆