動態規劃，設F[i,j]爲範圍1..i的集合元素之和大於等於j，不含連續自然數的集合個數

由於可能存在空集的情況，即計算過程中出現了k=-1，這是很不方便的，所以我修改了定義，把大於k方便的改成了大於等於k＋1。N=100，K=400時，結果是很大的，要使用高精度。

狀態轉移方程

F[i,j]= Sum { F[i-1,j], (包含第i個元素) F[i-2,j-i] (不包含第i個元素，j-i若小於0則爲F[i-2,0]) }

邊界條件

F[1,0]=2 //Ø,{1} F[1,1]=1 //{1} F[2,0]=3 //Ø,{1},{2} F[2,1]=2 //{1},{2} F[2,2]=1 //{2}

目標結果

F[N,K+1]

/* 
 * Problem: POI1997 lic
 * Author: Guo Jiabao
 * Time: 2008.11.29 14:29:00
 * State: Solved 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

template<int LIM,int MAX> class hp
{
    public:
        //vars
        int sect[MAX];
        int scnt;
        //constructors
        hp()
        {
            scnt=1;
            sect[0]=0;
        }
        //functions
        void copy(const hp<LIM,MAX> &A)
        {
            for (int i=0;i<A.scnt;i++)
                sect[i]=A.sect[i];
            scnt=A.scnt;
        }
        void copy(int A)
        {
            scnt=0;
            while (A)
            {
                sect[scnt++]=A % LIM;
                A /=LIM;
            }
        }
        void print()
        {
            int i,k;
            printf("%d",sect[scnt-1]);
            for (i=scnt-2;i>=0;i--)
            {
                k=LIM/10;
                while(sect[i]<k)
                {
                    printf("0");
                    k/=10;
                }
                if (sect[i])
                    printf("%d",sect[i]);
            }
        }
        void plus(hp<LIM,MAX> &A,int offset=0)
        {
            int sc=scnt > A.scnt + offset  ? scnt : A.scnt + offset;
            int i,j,up=0;
            for (i=0;i<sc;i++)
            {
                j=i - offset;
                if (j<0) continue;
                if (i>=scnt) sect[i]=0;
                if (j>=A.scnt) A.sect[j]=0;
                sect[i]+=A.sect[j] + up;
                up=sect[i] / LIM;
                sect[i]%=LIM;
            }
            scnt=sc;
            if (up) sect[scnt++]=up;
        }
        //operators
        void operator =(hp<LIM,MAX> A)
        {
            copy(A);
        }
        void operator =(int A)
        {
            copy(A);
        }
        void operator +=(hp<LIM,MAX> &A)
        {
            plus(A);
        }
};

typedef hp<1000000000,3> hpnum;

const int MAXN=101;
const int MAXK=402;

int N,K;
hpnum F[MAXN][MAXK];

void init()
{
    freopen("lic.in","r",stdin);
    freopen("lic.out","w",stdout);
    scanf("%d%d",&N,&K);
    K++;
}

void solve()
{
    int i,j;
    F[1][0]=2;
    F[1][1]=1;
    F[2][0]=3;
    F[2][1]=2;
    F[2][2]=1;
    for (i=3;i<=N;i++)
    {
        for (j=0;j<=K;j++)
        {
            F[i][j]=F[i-1][j];
            if (j-i>=0)
                F[i][j]+=F[i-2][j-i];
            else
                F[i][j]+=F[i-2][0];
        }
    }
}

int main()
{
    init();
    solve();
    F[N][K].print();
    return 0;
}

 n-k集合數

我們稱一個自然數集合X爲一個n-k集，如果它具有如下性質：

   1. 對於X中的每一個元素x有1 <= x <= n；
   2. X中的所有元素之和均大於k；
   3. X中不包括連續自然數。 

任務：

請寫一個程序：

    * 在文件中讀入兩個整數n和k；
    * 計算所有不同的n-k集的數目；
    * 將結果輸出到文件中。 

輸入格式：

在文件中的第一行包括兩個由空格分開的整數n和k，1 <= n <= 100，0 <= k <= 400。

輸出格式：

你應該在文件的第一行中輸出一個非負整數，爲所有不同的n-k集的數目。

樣例：

輸入

5 6

輸出

3