This post is written in Chinese. Please consider using Google Translate

动态规划，设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