HDU5914
题意：有n根长度从1到n的木棒，问最少拿走多少根，使得剩下的木棒无论怎样都不能构成三角形。
题解：斐波纳契数列，a+b=c恰好不能构成三角形，暴力就好，推一下也可以。
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
int t,n,cas=;
scanf("%d",&t);
int a[];
memset(a,,sizeof(a));
a[]=;
a[]=;
a[]=;
a[]=;
a[]=;
a[]=;
while(t--)
{
scanf("%d",&n);
int ans=;
for(int i=;i<=n;i++)
if(!a[i]) ans++;
printf("Case #%d: %d\n",cas++,ans);
}
return ;
}
切金条
一根金条长31厘米,如果把它切成数段,使其中的一段或几段能够接成长为1到31中任何整数的金条,请问要切几次?
题解：第一反应是斐波那契数列1 2 3 5 8 12，切5刀，结果错了，这道题应该用二进制做。123是不需要3的，因为12可以构成3，所以124是更好的选择。
这两道题好像，但是这是两道题，一定要仔细区分开。
1 2 4 8 16，和正好31，切4刀，答案是4。