斯德哥尔摩 的博客

斯德哥尔摩 的博客

P1415 拆分数列

posted on 2018-10-28 10:06:39 | under 刷题 |

P1415 拆分数列

第一步先求出最后的那个数最小为多少。

设$dp[i]$是处理到$i$时的最小末尾。

由于最小末尾是个很大的数,所以我们要用下标来表示出它。

而这个数一定在$i$终止,所以我们可以存它的起始位置。

于是重新定义状态:

设$dp[i]$是处理到$i$时的最小末尾的起始下标。

转移方程长这个样:$$dp[i]=\max\{\ j\ |\ j\in[1,i],num(j,i)>num(dp[j-1],j-1)\ \}$$

注意那个数字比较大小记得处理前导零。

第二步要求最后一个数确定的情况下,前面的数字按字典序尽量大的解。

同上,设$f[i]$是从$n$处理到$i$时的最大末尾的结束下标。

转移方程:$$f[i]=\max\{\ j\ |\ j\in[i,f[n]],num(i,j)<num(j+1,f[j+1])$$

初始化$f[dp[n]]=n$。

有一个坑点:$[1,9]$都不能与最后一个数合并成一个数,但是$0$可以。。。。

煮个栗子:

如果第一次$DP$计算出最小末尾为$50$,但输入是$\times\times\times...\times00050$。。。

这样上面的转移方程不会将$000$和$50$分成一组,因为$j\in[i,f[n]]$。

这样$000$所在状态就和状态定义不符,它没表示出最大末尾。

那不就凉了?

所以$DP$前要先将最后一个数的前导零全部特判。

复杂度$O(n^3)$。

然后站长lzn说:由于数据大部分为随机,实际运行效率接近$O(n^2)$。。。

附代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring>
#define MAXN 510
using namespace std;
int n;
int dp[MAXN],f[MAXN];
char str[MAXN];
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
    return date*w;
}
int check(int l1,int r1,int l2,int r2){
    if(r2==0)return 1;
    string s1,s2;
    while(str[l1]=='0')l1++;
    while(str[l2]=='0')l2++;
    for(int i=l1;i<=r1;i++)s1+=str[i];
    for(int i=l2;i<=r2;i++)s2+=str[i];
    if(s1.size()>s2.size())return 1;
    else if(s1.size()<s2.size())return 0;
    else{
        if(s1==s2)return -1;
        else return s1>s2;
    }
}
void solve_one(){
    for(int i=1;i<=n;i++){
        dp[i]=1;
        for(int j=i;j>=1;j--)if(check(j,i,dp[j-1],j-1)==1){
            dp[i]=max(dp[i],j);
            break;
        }
    }
}
void solve_two(){
    int m=0;
    f[dp[n]]=n;
    for(int i=dp[n]-1;i&&str[i]=='0';i--){
        f[i]=n;
        m++;
    }
    for(int i=dp[n]-1-m;i>=1;i--){
        f[i]=i;
        for(int j=dp[n]-1;j>=i;j--)if(check(i,j,j+1,f[j+1])==0){
            f[i]=max(f[i],j);
            break;
        }
    }
}
void print(int l,int r){
    for(int i=l;i<=r;i++)putchar(str[i]);
}
void work(){
    int now=1;
    solve_one();
    solve_two();
    while(now<=n){
        print(now,f[now]);
        now=f[now]+1;
        if(now<=n)putchar(',');
    }
    putchar('\n');
}
void init(){
    scanf("%s",str+1);
    n=strlen(str+1);
}
int main(){
    init();
    work();
    return 0;
}