The mook jong 计数DP

            The mook jong

ZJiaQ为了强身健体,决定通过木人桩练习武术。ZJiaQ希望把木人桩摆在自家的那个由1*1的地砖铺成的1*n的院子里。由于ZJiaQ是个强迫症,所以他要把一个木人桩正好摆在一个地砖上,由于木人桩手比较长,所以两个木人桩之间地砖必须大于等于两个,现在ZJiaQ想知道在至少摆放一个木人桩的情况下,有多少种摆法。

输入描述

输入有多组数据,每组数据第一行为一个整数n(1 < = n < = 60)

输出描述

对于每组数据输出一行表示摆放方案数
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 using namespace std;
 7 typedef long long LL;
 8 const int MS = 62;
 9
10 //令f[i]为最后一个木人桩摆放在i位置的方案,令s[i]为f[i]的前缀和。
11 //很容易就能想到f[i]=s[i-3]+1,s[i]=s[i-1]+f[i],而s[n]即是所求答案。
12 //本题唯一一个值得注意的点就是当n接近60时会爆int。
13
14 LL f[MS];
15 LL s[MS];
16
17 int main()
18 {
19         int n;
20         memset(f,0,sizeof(f));
21         memset(s,0,sizeof(s));
22         f[1] = 1;
23         f[2] = 1;
24         s[1] = 1;
25         s[2] = 2;
26         for(int i = 3;i<MS;i++)
27         {
28                 f[i] = s[i-3] + 1;
29                 s[i] = s[i - 1] + f[i];
30         }
31         while(scanf("%d",&n)!=EOF)
32         {
33                 printf("%d\n",s[n]);
34         }
35         return 0;
36 }
				



				
时间: 08-06

The mook jong 计数DP的相关文章

HDU - 5366 The mook jong (dp动态规划)

The mook jong Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 62    Accepted Submission(s): 40 Problem Description ![](../../data/images/C613-1001-1.jpg) ZJiaQ want to become a strong man, so h

HDU4815/计数DP

题目链接[http://acm.hdu.edu.cn/showproblem.php?pid=4815] 简单说一下题意: 有n道题,每到题答对得分为a[ i ],假如A不输给B的最小概率是P,那么A最少要得到多少分. 解题过程: 假设有n道题,每个题有两个状态,胜或者败,假设达到某个分数m有k(计数DP)种方式,那么最后是这个分数的概率是k/pow(2,n).那么A不输给B的概率就是小于等于m的分数的概率和. #include<bits/stdc++.h> const int maxn =

HDU 5366 The mook jong

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=5366 Problem Description ![](../../data/images/C613-1001-1.jpg) ZJiaQ want to become a strong man, so he decided to play the mook jong.ZJiaQ want to put some mook jongs in his backyard. His backyard con

The mook jong

ZJiaQ want to become a strong man, so he decided to play the mook jong.ZJiaQ want to put some mook jongs in his backyard. His backyard consist of n bricks that is 1*1,so it is 1*n.ZJiaQ want to put a mook jong in a brick. because of the hands of the

[sdut]2879计数dp……或者递推

第五届省赛C:colourful cupcakes N=60. 天真如我,居然在考虑搜索的算法/(ㄒoㄒ)/~~三叉树……3^60=10^24+……不计算考虑复杂度都是耍流氓>_< 再算了一下,感觉O(N^4)可以试试,60^4=10^8+……但是毕竟最差的情况嘛>_<,再看一下题解果然是4重循环的……计数……dp……(想到之前坚信的搜索不禁(*/ω\*)) 中间看到了一个三次动规六个方程的算法. 做麻烦了. 学长思路好快. #include<iostream> #in

HDU4901 The Romantic Hero 计数DP

2014多校4的1005 题目:http://acm.hdu.edu.cn/showproblem.php?pid=4901 The Romantic Hero Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 393    Accepted Submission(s): 150 Problem Description There i

[计数dp] ural 1114. Boxes

题目链接: http://acm.timus.ru/problem.aspx?space=1&num=1114 1114. Boxes Time limit: 0.6 second Memory limit: 64 MB N boxes are lined up in a sequence (1 ≤ N ≤ 20). You have A red balls and B blue balls (0 ≤ A ≤ 15, 0 ≤ B ≤ 15). The red balls (and the blu

ACM/ICPC算法训练 之 数学很重要-浅谈“排列计数” (DP题-POJ1037)

这一题是最近在看Coursera的<算法与设计>的公开课时看到的一道较难的DP例题,之所以写下来,一方面是因为DP的状态我想了很久才想明白,所以借此记录,另一方面是看到这一题有运用到 排列计数 的方法,虽然排列计数的思路简单,但却是算法中一个数学优化的点睛之笔. Poj1037  A decorative fence 题意:有K组数据(1~100),每组数据给出总木棒数N(1~20)和一个排列数C(64位整型范围内),N个木棒长度各异,按照以下条件排列,并将所有可能结果进行字典序排序 1.每一

CodeForces 176B Word Cut (计数DP)

Word Cut Time Limit:2000MS     Memory Limit:262144KB     64bit IO Format:%I64d & %I64u Submit Status Practice CodeForces 176B Description Let's consider one interesting word game. In this game you should transform one word into another through specia