HDU 5914 Triangle

题目来源：2016 CCPC 长春站

题意：青蛙先生想用n个长度为1~n的木棍来组成一些三角形，但是有一个坏蛋就想破坏青蛙先生的好事，请问在这n个木棍中至少偷出来几个木棍使得青蛙先生无法再用剩下的一些木棍组成三角形

思路：假设 p[i] = x 代表有i个木棍至少偷走x个剩下的木棍就无法组成三角形

可以先手写出 i 较小的答案

p[1] = 0

p[2] = 0

p[3] = 0

p[4] = 1

p[5] = 1

p[6] = 2

p[7] = 3

p[8] = 3

然后会发现一个比较有趣的问题，只有i为fib数的时候 x 不变，否则每次都是x+1，直接打一个答案打表

/*************************************************************************

    > File Name: D.cpp

    > Author:    WArobot

    > Mail:      768059009@qq.com

    > Created Time: 2017年04月15日 星期六 21时11分06秒

 ************************************************************************/

#include<bits/stdc++.h>

using namespace std;

int p[21] = { 0,0,0,0,1,1,2,3,3,4,5,6,7,7,8,9,10,11,12,13,14 };

int t,n,kase;

int main(){

	kase = 0;

	scanf("%d",&t);

	while(t--){

		scanf("%d",&n);

		printf("Case #%d: %d\n",++kase,p[n]);

	}

	return 0;

}

巴特西

HDU 5914 Triangle

最新文章

热门文章