URAL1017[The Staircases]

把N分堆,每堆不同,一共有多少分法?
f[n][i]=N分堆后最大的为i一共有几种分法
f[n][n]=1
f[n][i]=sum{f[n-i][j],1<=j<i<n}
answer=sum{f[n][i],1<=i<=n}-1
(减一是减去只有一堆的情况)
CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-3-16


DESCRIPTION:


$DESCRIPTION


*/


#include <iostream>


using std::cin;


using std::cout;


using std::endl;


#include <sstream>


using std::stringstream;


#include <vector>


using std::vector;


#include <string>


using std::string;


#include <stack>


using std::stack;


#include <queue>


using std::queue;


#include <map>


using std::map;


using std::pair;


using std::make_pair;


#include <algorithm>


using std::sort;


#include <cassert>


//using std::assert;


 


class Application


{


      int N;


      public:


      Application()


      {


                    cin>>N;


      }


      int run()


      {


          //N分堆,每堆不同,一共有多少分法?


          //f[n][i]=N分堆后最大的为i一共有几种分法


          //f[n][n]=1


          //f[n][i]=sum{f[n-i][j],1<=j<i<n}


          //answer=sum{f[n][i],1<=i<=n}-1


         


          vector<vector<long long int> > f(N+1,vector<long long int>(N+1,0));


          for (int i=1;i<=N;i++) f[i][i]=1;


          for (int n=1;n<=N;n++)


              for (int i=1;i<n;i++)


                  for (int j=1;j<i;j++)


                      f[n][i]+=f[n-i][j];


          long long int answer=-1;


          for (int i=1;i<=N;i++)


              answer+=f[N][i];


          cout<<answer<<endl;


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}