51问答网 > NOIP2008提高组初赛试题:第三大题的第2问（详解）和做完善程序的技巧~！！！跪谢了！！！

NOIP2008提高组初赛试题:第三大题的第2问（详解）和做完善程序的技巧~！！！跪谢了！！！

2024-12-19 14:13:39

推荐回答（1个）

回答1：

3060种，此题类似集合取数问题：
设f(n,k)是从集合{1，2，。。。，n}中能够选择的没有两个连续整数的k个元素子集的数目，求递归式f(n,k)。

N有两种情况：
① 当n在子集时，则n-1一定不在子集中，即在{1，2，。。。，n-2}中选k-1个元素，数目为f(n-2,k-1)。
② 当n不在子集中时，则在{1，2，。。。，n-1}中选k个元素，数目为f(n-1,k)。
所以：f(n,k)= f(n-2,k-1) +f(n-1,k)
边界条件：F(n,1)=n, f(n,k)=0 ( n<=k)

① inc(j); (或者j := j+1;)
② a[i,j] > k
③ a[i,j] < k
④ answerx := i;
⑤ answery := j;