最优分解（动态规划）.cpp

来自「贪心算法解一系列算法经典问题」· C++ 代码 · 共 36 行

#include   <stdio.h>   
#include   <math.h>   

main()   
{   
  unsigned   int   n;   
  int   g[500],*p=g,l=0;   
  float   t;   
  printf("请输入一个整数： ");
  scanf("%d",&n);   
  
  if(n>=0 && n<=4)   
       printf("%d   ",n);                 /*如果N小于5直接打印出N*/   
  else
	  {   
           t=sqrt((long)n*8+17);   
           if(t==(int)t)
		   {   
                l=1;n--;   
		   }   
           while(n>=4)
		   {                         /*从后往前推出结果*/   
                t=sqrt((long)n*8+9);   
                if(t==(int)t)   
				   *p=(t-1)/2;   
                else   
                   *p=(int)((t-1)/2)+1;   
                n-=*p;p++;   
		   }   
          *p=n;   
           if(l==1)
			   g[0]++;   
           for(l=p-g;l>=0;l--)   
                  printf("%d   ",g[l]);     /*打印结果*/   
	  }   
  }