POI 1997 n-k集合数
动态规划，设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
上次修改时间 2017-02-03