题目背景
【为了响应党*勤节俭、反铺张的精神,题目背景描述故事部分略去^-^】
题目描述
给出一列数字,需要你添加任意多个逗号将其拆成若干个严格递增的数。如果有多组解,则输出使得最后一个数最小的同时,字典序最大的解(即先要满足最后一个数最小;如果有多组解,则使得第一个数尽量大;如果仍有多组解,则使得第二个数尽量大,依次类推……)。
输入输出格式
输入格式:
共一行,为初始的数字。
输出格式:
共一行,为拆分之后的数列。每个数之间用逗号分隔。行尾无逗号。
输入输出样例
[1]
3456
[2]
3546
[3]
3526
[4]
0001
[5]
100000101
[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]+;
}
}