BNU34058——干了这桶冰红茶！—————

干了这桶冰红茶！

Time Limit: 1000ms

Memory Limit: 65536KB

64-bit integer IO format: %lld Java class name: Main

Type:

None

Graph Theory

    2-SAT

    Articulation/Bridge/Biconnected Component

    Cycles/Topological Sorting/Strongly Connected Component

    Shortest Path

        Bellman Ford

        Dijkstra/Floyd Warshall

    Euler Trail/Circuit

    Heavy-Light Decomposition

    Minimum Spanning Tree

    Stable Marriage Problem

    Trees

    Directed Minimum Spanning Tree

    Flow/Matching

        Graph Matching

            Bipartite Matching

            Hopcroft–Karp Bipartite Matching

            Weighted Bipartite Matching/Hungarian Algorithm

        Flow

            Max Flow/Min Cut

            Min Cost Max Flow

DFS-like

    Backtracking with Pruning/Branch and Bound

    Basic Recursion

    IDA* Search

    Parsing/Grammar

    Breadth First Search/Depth First Search

    Advanced Search Techniques

        Binary Search/Bisection

        Ternary Search

Geometry

    Basic Geometry

    Computational Geometry

    Convex Hull

    Pick's Theorem

Game Theory

    Green Hackenbush/Colon Principle/Fusion Principle

    Nim

    Sprague-Grundy Number

Matrix

    Gaussian Elimination

    Matrix Exponentiation

Data Structures

    Basic Data Structures

    Binary Indexed Tree

    Binary Search Tree

    Hashing

    Orthogonal Range Search

    Range Minimum Query/Lowest Common Ancestor

    Segment Tree/Interval Tree

    Trie Tree

    Sorting

    Disjoint Set

String

    Aho Corasick

    Knuth-Morris-Pratt

    Suffix Array/Suffix Tree

Math

    Basic Math

    Big Integer Arithmetic

    Number Theory

        Chinese Remainder Theorem

        Extended Euclid

        Inclusion/Exclusion

        Modular Arithmetic

    Combinatorics

        Group Theory/Burnside's lemma

        Counting

    Probability/Expected Value

Others

    Tricky

    Hardest

    Unusual

    Brute Force

    Implementation

    Constructive Algorithms

    Two Pointer

    Bitmask

    Beginner

    Discrete Logarithm/Shank's Baby-step Giant-step Algorithm

    Greedy

    Divide and Conquer

Dynamic Programming
              Tag it!

BNUCIST的HWQ大神特别钟爱冰红茶这种神棍的饮料，有一天打Dota暴虐他寝室的WL后，决定大喝一顿庆祝一下。他决定用一种神棍的方式来喝冰红茶，那就是每口只喝1升，或者2升，或者3升（PS：HWQ大神真的能喝这么多= =）。爱思考的HWQ突然想知道，对于一桶整数升的冰红茶，他可以有多少种方案喝光，但似乎他不能马上想出解决的办法，纠结的他不知道答案他就喝不下去了。聪明的你快帮帮他吧。

Input

输入一个整数T,代表数据组数。

对于每一组数据，输入一个整数N，1<=N<=30，表示这桶冰红茶有N升。

Output

对于每个N，输出一个整数，代表方案数。

Sample Input

1

3

Sample Output

Hint

对于样例，3升的冰红茶，他可以（1）每次喝1升，连喝3口；（2）第一口喝1升，第二口喝2升；（3）第一口喝2升，第二口喝1升；（4）一口就喝掉3升。所以共有4种方案。

Source

2013年北京师范大学新生程序设计竞赛

解题思路：通过前面的递推出后边的。对于任意n可分为{{1，n-1}，{2，n-2}，{3，n-3}}，所以sum[i]=sum[i-1]+sum[i-2]+sum[i-3]；

#include<bits/stdc++.h>

using namespace std;

int sum[50];

int main(){

    int T;

    scanf("%d",&T);

    sum[0]=1;sum[1]=1;sum[2]=2;

    for(int i=3;i<32;i++){

        sum[i]=sum[i-1]+sum[i-2]+sum[i-3];

    }

    while(T--){

        int n;

        scanf("%d",&n);

        printf("%d\n",sum[n]);

    }

    return 0;

}

巴特西

BNU34058——干了这桶冰红茶！——————【递推】