代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 110
#define clean(x,y); memset(x,y,sizeof(x));
#define cc(x); memset(&x,0,sizeof(x));
using namespace std;
char a[maxn];
long p[maxn],n;
void build()
{
clean(p,0);
long i,j;
n=strlen(a);
for(i=1;i<=n;i++)
{
p[i]=a[i-1]-'0';
}
}
long f[maxn];
struct line{
long m[maxn];
bool operator<(const line& t)
{
if(m[0]<t.m[0])
return true;
if(m[0]==t.m[0])
{
for(long i=m[0];i>=1;i--)
{
if(m[i]<t.m[i])return true;
if(m[i]>t.m[i])return false;
}
}
return false;
}
line operator*(const long &k)const
{
long i,j;
line x;
cc(x);
if(k==0)
{
x.m[0]=1;
return x;
}
x.m[0]=m[0];
for(i=1;i<=m[0];i++)
{
x.m[i]+=m[i]*k;
x.m[i+1]=x.m[i]/10;
x.m[i]%=10;
}
i=x.m[0]+1;
while(x.m[i]!=0)
{
x.m[i+1]+=x.m[i]/10;
x.m[i++]%=10;
}
x.m[0]=i-1;
return x;
}
line operator+(const line &t)const
{
line x;
cc(x);
long i;
x.m[0]=max(m[0],t.m[0]);
for(i=1;i<=x.m[0];i++)
{
x.m[i]+=m[i]+t.m[i];
x.m[i+1]=x.m[i]/10;
x.m[i]%=10;
}
i=x.m[0]+1;
while(x.m[i]!=0)
{
x.m[i+1]=x.m[i]/10;
x.m[i++]%=10;
}
x.m[0]=i-1;
return x;
}
void free()
{
long i=m[0];
while(m[i]==0&&i!=1)
{
i--;
}
m[0]=i;
}
}b[maxn];
long gg,great[maxn],bb,better[maxn];
void dfs(long x,line lim)
{
long i,j;
if(f[x]==-1)
{
i=gg;j=bb;
while(i>=0&&j>=0)
{
if(great[i]>better[j])
return;
if(great[i]==better[j])
{
i--;j--;
continue;
}
for(i=1;i<=bb;i++)
great[i]=better[i];
gg=bb;
return;
}
return;
}
line ans=b[x],temp;
i=f[x];
while(ans<lim)
{
bb++;
better[bb]=i;
dfs(i,ans);
bb--;
i--;
if(i<0)return;
if(p[i+1]!=0)
{
cc(temp);
temp.m[0]=x-i;
temp.m[x-i]=p[i+1];
ans=ans+temp;
}
}
}

int main()
{
freopen("incsq.in","r",stdin);
freopen("incsq.out","w",stdout);
long i,j;
line ans,flag;
scanf("%s",a);
build();
f[0]=-1;
cc(b[0]);
b[0].m[0]=1;
for(i=1;i<=n;i++)
{
cc(ans);cc(flag);
ans.m[0]=1;
flag.m[0]=1;flag.m[1]=1;
for(j=i;j>=1;j--)
{
ans=ans+flag*p[j];
flag=flag*10;
if(b[j-1]<ans)
{
b[i]=ans;
f[i]=j-1;
break;
}
}
}
clean(great,-1);clean(better,-1);
gg=bb=0;
i=f[n];
bb++;
better[bb]=i;
dfs(i,b[n]);
bb--;
while(p[i]==0)
{
if(i==0)break;
bb++;
better[bb]=i;
dfs(i-1,b[n]);
bb--;
i--;
}
j=gg-1;
for(i=1;i<=n;i++)
{
cout<<p[i];
if(j>0)
{if(i==great[j])
{
cout<<',';
j--;
}}
}
return 0;
}

这道题建议所有马上要参加比赛的同学就不要做了，做了你会后悔你为什么不信春哥。
强烈建议那些跟我一样眼高手低的人做一下，联系一下你的编码能力，并且告诉你不要随便说话。
最后@doveccl orz王杰凯

跟我有什么关系，~(>_<)~

这道题目是典型的动归加dfs搜索。用动归得到最优解之后倒搜状态，用之前动归结果来剪枝。