# 斯德哥尔摩 的博客

### P1415 拆分数列

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

P1415 拆分数列

#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];
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;
}