递推DP URAL 1225 Flags

淩亂°似流年 2022-01-09 06:04 164阅读 0赞

[题目传送门][Link 1]

1 /*
     2     1 r; 2 b; 3 w
     3     2不能在最前面，所以dp[1] = 2;    dp[2] = 2: 13 or 31
     4 
     5     dp[i] = dp[i-1] + dp[i-2];
     6     只加1或3时，总数dp[i-1];    只加12或32时，总数dp[i-2];
     7     详细解释：http://www.cnblogs.com/vongang/archive/2011/09/30/2196847.html
     8 */
     9 #include <cstdio>
    10 #include <iostream>
    11 #include <algorithm>
    12 #include <cstring>
    13 using namespace std;
    14 
    15 const int MAXN = 55;
    16 const int INF = 0x3f3f3f3f;
    17 long long dp[MAXN];
    18 
    19 int main(void)        //URAL 1225 Flags
    20 {
    21     //freopen ("A.in", "r", stdin);
    22 
    23     int n;
    24     while (scanf ("%d", &n) == 1)
    25     {
    26         memset (dp, 0, sizeof (dp));
    27 
    28         dp[1] = 2;    dp[2] = 2;
    29         for (int i=3; i<=n; ++i)
    30         {
    31             dp[i] = dp[i-1] + dp[i-2];
    32         }
    33 
    34         printf ("%I64d\n", dp[n]);
    35     }
    36 
    37     return 0;
    38 }

转载于:https://www.cnblogs.com/Running-Time/p/4482698.html

[Link 1]: http://acm.timus.ru/problem.aspx?space=1&num=1225

发表评论取消回复

表情：

评论列表（有 0 条评论，164人围观）

还没有评论，来说两句吧...

相关阅读

相关 51nod 1201 递推+dp

题意：将N分为若干个不同整数的和，有多少种不同的划分方式，例如：n = 6，\{6\} \{1,5\} \{2,4\} \{1,2,3\}，共4种。由于数据较大，输出Mod

秒速五厘米/ 2022年08月19日 15:19/ 0 赞/ 184 阅读

相关 51nod 1270 递推+dp

题意：数组A包含N个元素A1, A2......AN。数组B包含N个元素B1, B2......BN。并且数组A中的每一个元素Ai，都满足1 <= Ai <= B

叁歲伎倆/ 2022年08月19日 15:17/ 0 赞/ 163 阅读

相关 51nod1202 dp+递推

题意：子序列的定义：对于一个序列a=a\[1\],a\[2\],......a\[n\]。则非空序列a'=a\[p1\],a\[p2\]......a\[pm\]为a的一个子序

桃扇骨/ 2022年08月19日 14:28/ 0 赞/ 144 阅读

相关 hdu5286 dp+递推

题意：有n个人，每个人有一个value值，有两扇门A,B分别各有一个value，现在要讲n个人分为两组分别从两个门进入，要求是每组人的value值的和（迭代的求，直至变为一

本是古典何须时尚/ 2022年08月19日 14:28/ 0 赞/ 150 阅读

相关 hdu5375 dp+递推

题意：给出一段二进制码，其中有些位置的数字不确定用"?"表示，这些位置可以为0也可以为1，然后将这个数字的所有可能转化为相应的格雷码，格雷码对应的数字串中位置为i的数字是1

╰半夏微凉°/ 2022年08月19日 14:23/ 0 赞/ 157 阅读

相关 hdu4489 dp+递推

题意：有n个高矮不同的士兵，现在要将他们按高，矮依次排列，问有多少种情况。分析：组合dp问题。假设n个士兵的身高分别为1，2......n。我们现在考虑n个

待我称王封你为后i/ 2022年08月19日 14:21/ 0 赞/ 162 阅读

相关 URAL 1057 (数位dp)

问题描述: Create a code to determine the amount of integers, lying in the set \[ X; Y\] and

比眉伴天荒/ 2022年06月04日 05:16/ 0 赞/ 182 阅读

相关 URAL 1036(数位dp)

问题描述: You are given a number 1 ≤ N ≤ 50. Every ticket has its 2 N-digit number. We call

矫情吗；*/ 2022年06月04日 05:15/ 0 赞/ 224 阅读

相关 CF 570E dp递推

题意：给一个n\m的小写字母地图，找从（1，1）到（n，m）点非升路径，且路径组成的字符串是回文串的路径个数。思路：考虑从两端同时走，然后在中间相遇，走的步数是确定的，

浅浅的花香味﹌/ 2022年05月07日 23:30/ 0 赞/ 159 阅读

相关递推DP URAL 1225 Flags

[题目传送门][Link 1] 1 / 2 1 r; 2 b; 3 w 3 2不能在最前面，所以dp[1] = 2; dp[

淩亂°似流年/ 2022年01月09日 06:04/ 0 赞/ 165 阅读