http://poj.org/problem?id=1239
题意：
给出一串序列，现在要添加逗号作为分隔符，使得序列是递增序列，然后让最后一个数尽量小，第一个数尽量大。
思路：
先从头到尾进行一次dp，d【i】表示分析到第i位时往前的最小长度，这样一来，d【n】就表示最后一位的最小长度。
在满足了最后一位尽量小的情况下，我们再从尾到头进行一次dp，此时d【i】表示分析到第i位时往后的最大长度。思路和第一次dp是差不多的。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<sstream>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const int INF = 0x3f3f3f3f;
const int maxn = + ; int d[maxn];
char s[maxn]; bool judge(int i, int j, int x, int y) //判断【i，j】是否大于【x，y】
{
int len1=j-i+;
int len2=y-x+; while(s[i]=='') {i++;len1--;}
while(s[x]=='') {x++;len2--;} if(len1>len2) return true;
else if(len1<len2) return false;
else
{
for(int k=; k<len1;k++)
{
if(s[k+i]>s[x+k]) return true;
else if(s[k+i]<s[x+k]) return false;
}
}
return false;
} int main()
{
//freopen("in.txt","r",stdin);
while(~scanf("%s",s+))
{
int n=strlen(s+);
if(n== && s[]=='') break; //从头到尾找最小长度
for(int i=;i<=n;i++)
{
d[i]=i;
for(int j=i-;j>=;j--)
{
if(judge(j+,i,j-d[j]+,j))
{
d[i]=i-j;
break;
}
}
} //从尾到头找最大长度
int t=n-d[n]+; //[t,n]已经是决定了的，不能改变
d[t]=d[n];
for(int i=n-d[n];i>=;i--)
{
if(s[i]=='')
{
d[i]=d[i+]+;
continue;
}
for(int j=t;j>i;j--)
{
if(judge(j,j+d[j]-,i,j-))
{
d[i]=j-i;
break;
}
}
} int tmp=d[]+;
for(int i=;i<=n;i++)
{
if(tmp==i)
{
printf(",");
tmp=d[i]+i;
}
printf("%c",s[i]);
}
printf("\n");
}
return ;
}