最小m段和问题.cpp

动态规划解一系列经典问题

#include     <stdio.h>       
  #include     <stdlib.h>       
  #include     <iostream.h>       
  #include     <fstream.h>       
  #include     <iomanip.h>       
  #define     MAXINT     65535;       
  struct     kao       
  {       
                        int     biaozhi;       
                        int     dir;       
  };       
  struct     kao     first[2810][2810];       
  int     m,n,sum,s[9000000];       
  void     value(int     start,int     finish)       
  {       
                  
            int     i,t,min,j,middle;       
              
            if((start<=n)&&(finish==0))       
                            {first[start][finish].biaozhi=MAXINT;return;}       
            else     if((start>n)&&(finish==0))           
                        {first[start][finish].biaozhi=0;return;}       
            t=0;       
            min=MAXINT;       
            for(i=start;i<=n-finish+1;i++)       
            {       
                    t=t+s[i];       
                    if(first[i+1][finish-1].biaozhi==0)       
                        value(i+1,finish-1);       
                    if(first[i+1][finish-1].biaozhi>t)           
                        middle=first[i+1][finish-1].biaozhi;       
                    else     middle=t;       
                    if     (middle<min)       
                            {min=middle;j=i;}       
            }       
            first[start][finish].biaozhi=min;       
                          
            sum=min;       
  }       
      
  void     main()       
  {                         int     la=1;           
                        ofstream     fout;       
                        ifstream     fin("input.txt");       
                        fin>>n     >>m;       
  for(int     l=0;l<n;l++)       
  {               
                        fin>>s[l+1]     ;}       
  value(1,m);       
  fout.open("output.txt");       
                        fout<<sum<<endl;       
                        fout.close();       
                        fin.close();       
  }