有一串数字,在它们之间加逗号来分隔,使之成为一个上升序列。
要求最后一个数尽可能的小,如果有多个满足要求,则使第一个数尽可能大;如果还有多个,则使第二个最大,依此类推。
感觉这是一道很经典的线性DP题(因为做的太少了)。
思路就是首先保证后一个数尽量大于前一个数,一旦满足条件就去找下一个数。
然后就找到了能满足条件的而且最小的最后一个数,然后我们还需要倒着推使得,前面的数尽量大并且还满足条件。
感觉这道题代码实现极其重要。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
char s[1010],dp[1010];
inline int Judge(int x,int y,int m,int n){
while(x<=y&&s[x]==0) x++;
while(m<=n&&s[m]==0) m++;//去除前导0,思路是不是更高精度差不多。。
if(x>y) return 0;
if(m>n) return 1;//如果消失了
if((y-x)!=(n-m)) return (y-x)>(n-m);//判断位数
for(int i=x,j=m;i<=y&&j<=n;++i,++j){
if(s[i]!=s[j]) return s[i]>s[j];//从高位到低位扫一遍
}
return 0;
}
int main (){
while(scanf(" %s",s+1)!=EOF){
int n=strlen(s+1);
if(n==1&&s[1]=='0') return 0;
for(int i=1;i<=n;++i) s[i]-='0';
dp[1]=1;//dp[i]表示以i结尾,以i-dp[i]+1开头的数字
for(int i=2;i<=n;++i){//保证满足条件并且后面的数字尽量小
dp[i]=i;//默认如果无法大于前面的任何数就从1开始
for(int j=i-1;j>=1;--j){//以j结尾
if(Judge(j+1,i,j-dp[j]+1,j)){//判断以j+1开头,i结尾的数能否满足条件
dp[i]=i-j;
break;//尽量小,所以一旦找到就退出
}
}
}
int end=n-dp[n];//最后一个数字不变
dp[end+1]=dp[n];//含义变了,表示以i开头,i+dp[i]-1结尾的数字
//保证满足条件,并且使得前面的数字尽量大
//因为最后一个数字固定了,所以找后面尽量大,并且小于后面的数
for(int i=end;i>=1;--i){
if(s[i]==0){
dp[i]=dp[i+1]+1;//前导0直接加
continue;
}
for(int j=end+1;j>i;--j){
if(Judge(j,j+dp[j]-1,i,j-1)){//跟上面类似
dp[i]=j-i;
break;//因为是从后往前扫,所以一旦找到就退出,保证尽量大
}
}
}
for(int i=1,fina=i+dp[i]-1;i<=n;++i){
printf("%d",s[i]);
if(i==fina&&i!=n) printf(","),fina=i+dp[i+1];
}
putchar('\n');
}
return 0;
}
0 条评论