# Triangle

## 题目连接：

http://acm.hdu.edu.cn/showproblem.php?pid=5914

## Description

Mr. Frog has n sticks, whose lengths are 1,2, 3⋯n respectively. Wallice is a bad man, so he does not want Mr. Frog to form a triangle with three of the sticks here. He decides to steal some sticks! Output the minimal number of sticks he should steal so that Mr. Frog cannot form a triangle with
any three of the remaining sticks.

## Input

The first line contains only one integer T (T≤20), which indicates the number of test cases.

For each test case, there is only one line describing the given integer n (1≤n≤20).

## Output

For each test case, output one line “Case #x: y”, where x is the case number (starting from 1), y is the minimal number of sticks Wallice should steal.

3
4
5
6

Case #1: 1
Case #2: 1
Case #3: 2

## 代码

``````#include<bits/stdc++.h>
using namespace std;
const int maxn = 25;
int dp[maxn];
int main()
{
dp=1,dp=1,dp=1,dp=1,dp=1,dp=1,dp=1;
for(int i=1;i<=20;i++)
dp[i]+=dp[i-1];
for(int i=1;i<=20;i++)
dp[i]=i-dp[i];
int t;
scanf("%d",&t);
for(int cas=1;cas<=t;cas++){
int x;scanf("%d",&x);
printf("Case #%d: %d\n",cas,dp[x]);
}
}``````
原文作者：qscqesze
原文地址: https://www.cnblogs.com/qscqesze/p/6094847.html
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。