POI 1997 n-k集合數
本文正體字版由OpenCC轉換
動態規劃，設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