洛谷P1415 拆分数列[序列DP 状态 打印]

时间：2023-11-25 17:19:56

题目背景

【为了响应党*勤节俭、反铺张的精神，题目背景描述故事部分略去^-^】

题目描述

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

输入输出格式

输入格式：

共一行，为初始的数字。

输出格式：

共一行，为拆分之后的数列。每个数之间用逗号分隔。行尾无逗号。

输入输出样例

输入样例#1： 
[1]

3456

[2]

3546

[3]

3526

[4]

0001

[5]

100000101
输出样例#1： 
[1]

3,4,5,6

[2]

35,46

[3]

3,5,26

[4]

0001

[5]

100,000101

说明

【题目来源】

lzn改编

【数据范围】

对于10%的数据，输入长度<=5

对于30%的数据，输入长度<=15

对于50%的数据，输入长度<=50

对于100%的数据，输入长度<=500

看了题解

官方题解：

《拆分数列》解题报告

By lzn 动态规划常规题。

第一步先求出最后的那个数最小为多少。（为了叙述方便，记T(i,j)表示从原数列下标i取到j的数字组成的数。）只需正向dp一次，dp1[i]表示前i个数字分成任意多个递增数且最后的数最小时，最后的数为T(dp1[i],i)。则dp1[i]=max(j)，(T(dp1[j-1],j-1)<T(j,i))。

第二步要求最后一个数确定的情况下，前面的数字按字典序尽量大的解。类似上面的方法反向动归一次即可。

算法复杂度o(l^3)。由于数据大部分为随机，实际运行效率接近l^2。

我的实现是：

第一步，d[i]表示以i结尾的序列最后一个数最小的起始下标d[i]，转移同上

第二步，f[i]表示从i开始的序列第一个数最大的终止下标f[i]，转移f[i]=max{j|T(i,j)<T(j+1,f[j+1])}

打印时从1开始沿f走就行了

注意：

1.字符串比较处理前导0，并且我在遇到全0串时返回了false，因为这样的划分不合法

2.初始化d[i]=1

3.第一次95分，有一个数据1234050，我的程序无法把050划分成一个

解决措施是把最后一个数前面的前导0的f值都指向n

经验：

1.分两步求解

2.非常特别的状态表示，无法直接保存数的大小，所以保存序列中下标

3.字符处理成数字注意前导0

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

typedef long long ll;

const int N=,INF=2e9+;

char s[N];

int n,a[N];

bool small(int l1,int r1,int l2,int r2){

    while(l1<=r1&&a[l1]==) l1++;

    while(l2<=r2&&a[l2]==) l2++;

    if(r1-l1+==||r2-l2+==) return false;//hello

    if(r1-l1+<r2-l2+) return true;

    if(r1-l1+>r2-l2+) return false;

    int len=r1-l1+;

    for(int i=;i<len;i++){

        if(a[l1+i]<a[l2+i]) return true;

        if(a[l1+i]>a[l2+i]) return false;

    }

    return false;

}

int d[N];

void dp1(){

    for(int i=;i<=n;i++){

        d[i]=;

        for(int j=i;j>=;j--)

            if(small(d[j-],j-,j,i)) {d[i]=j;break;}

    }

    //for(int i=1;i<=n;i++) printf("d %d %d\n",i,d[i]);

}

int f[N];

void dp2(){

    f[d[n]]=n;int zero=d[n];

    while(a[zero-]==) f[zero-]=n,zero--;

    for(int i=d[n]-;i>=;i--){

        for(int j=d[n]-;j>=i;j--)

            if(small(i,j,j+,f[j+])) {f[i]=j;break;}

    }

    //for(int i=1;i<=n;i++) printf("f %d %d\n",i,f[i]);

    //system("pause");

}

int main(){

    scanf("%s",s+);

    n=strlen(s+);

    for(int i=;i<=n;i++) a[i]=s[i]-'';

    dp1();

    dp2();

    int pos=,flag=;

    while(pos<=n){//printf("pos %d %d\n",pos,f[pos]);

        if(flag) putchar(',');

        flag=;

        for(int i=pos;i<=f[pos];i++) printf("%d",a[i]);

        pos=f[pos]+;

    }

}

相关文章