在【1,n】中,可以删去最多多少个数,可以使得剩下的数字构不成三角形的三条边
三角形:a+b<=c这样,才是构不成三角形的a,b,c三边
那么,极限条件是什么呢?!等于号
a+b=c
取a=1,b=2(前两个,肯定要尽量小)那么得到的FIB数列(讲道理的话,这个题的n设计的得太小了,如果搞大一点更容易知道是数学题)
1,2,3,5,8,13是可能取出的最多的三角形的边
所以,答案就是打表就好:
#include<bits/stdc++.h>
using namespace std;
int ans[21] = {0,0,0,0,1,1,2,3,3,4,5,6,7,7,8,9,10,11,12,13,14};
int main(){
int t,n;
scanf("%d",&t);
for(int Case=1;Case<=t;Case++){
scanf("%d",&n);
printf("Case #%d: %d\n",Case,ans[n]);
}
return 0;
}