increasingseauence.txt

这是一个关于sequence不断增大的问题,虽然不是太大但很是精辟.

#include<stdio.h>
#include<string.h>
#define MAXN 100
char st[MAXN];
int n;
double dat[MAXN][MAXN];
int can[MAXN][MAXN];
int next[MAXN];
double nowmax[MAXN];
int init()
{
  scanf("%s",st);
  n=strlen(st);
  if(st[0]=='0' && n==1) return 0;
  for(int i=0; i<n; i++)
   for(int j=i; j<n; j++)
   {
      dat[i][j]=0;
      for(int k=i; k<=j; k++) dat[i][j]=dat[i][j]*10+(st[k]-'0');
   }
  return 1;
}
void make_it()
{
  int i,j,k;
  for(i=0; i<n; i++) can[0][i]=1;
  for(i=1; i<n; i++)
   for(j=i; j<n; j++)
   {
     k=j-1;can[i][j]=0;
     while(k>=0 && dat[k][i-1]<dat[i][j])
       if(can[k--][i-1]) { can[i][j]=1;break;}
   }
  k=n-1; while(!can[k][n-1]) k--;
  next[k]=n-1;
  memset(nowmax,0,sizeof(nowmax));
  nowmax[k]=dat[k][n-1];   k--;
  while(k>=0 && st[k]=='0'){ nowmax[k]=dat[k][n-1]; next[k]=n-1; k--;}
  for(i=k; i>=0; i--)
   for(j=i; j<n; j++)
    if(dat[i][j]<nowmax[j+1])
    {
      nowmax[i]=dat[i][j];
      next[i]=j;
    }
  i=0;
  while(i<n)
  {
    for(j=i; j<=next[i]; j++) putchar(st[j]);
    i=next[i]+1;
    if(i<n) putchar(','); else putchar('\n');
  }
}
int main()
{
  while(init())
    make_it();
  return 0;
}