HDU 5366 - The mook jong


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

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 mook jong, the distance of two mook jongs should be equal or more than 2 bricks. Now ZJiaQ want to know how many ways can ZJiaQ put mook jongs legally(at least one mook jong).
Input
There ar multiply cases. For each case, there is a single integer n( 1 < = n < = 60)
Output
Print the ways in a single line for each case.
Sample Input
1 2 3 4 5 6
Sample Output
1 2 3 5 8 12
http://www.lai18.com/content/4329060.html
在1*n的院子里铺有1*1的地板,在地板上里放置木人桩,木人桩之间至少相隔2快地板,问至少放置一个木人桩的情况下,可能的情况

http://www.cnblogs.com/fenice/p/5321679.html

方法一:

  区间dp。
  dp[i][j]表示前i个地砖放j个木人桩(其中第i个地砖肯定有放东西,要不然就不会是dp[i][j],而是dp[k][j](k<i) )
  则易得转移方程 dp[i][j]=sum(dp[k][j-1]),其中k<i-2;
  初始化要注意:dp[i][1]=1,而其他则都清零。

http://blog.csdn.net/david_jett/article/details/47376251
  状态转移方程: dp[i]=dp[i-1]+dp[i-3]+1。
  dp[i]的含义是到i这个位置为止,有多少种方案数,也就是答案。因为dp表示的是合法的解,所以之前一定已经至少放了一个木桩了。dp[i-1]代表的是当前位置i不放木桩,
dp[i-3]代表的是当前位置放,因为间隔为2,所以不论前面第三个位置有没有,当前位置i都可以放置1个木桩,至于最后加上的一个1,开始没怎么理解,其实它代表的是前面i-1
个位置都没放置木桩,而在当前位置i放置一个木桩,这也是一组合法的解,故加上1。
  1. long long dp[65]={0,1,2,3};  
  2. void init()  
  3. {  
  4.   for(int i=4;i<=60;i++)  
  5.       dp[i]=dp[i-1]+dp[i-3]+1;  
  6. }  
  7. int main()  
  8. {  
  9.     init();  
  10.     int n;  
  11.     while(~scanf("%d",&n))  
  12.     {  
  13.         printf("%lld\n",dp[n]);  
  14.     }  
  15.     return 0;  
  16. }  
http://www.it610.com/article/5474922.htm
令f[i]为最后一个木人桩摆放在i位置的方案,令s[i]为f[i]的前缀和,即s[i]=f[0]+f[1]+...+f[i]。很容易就能想到f[i]=s[i-3]+1,因为最后一个木人放到最后一个位置,因此只有i-3个木人是可用的,再加上最后一种情况,s[i]=s[i-1]+f[i],而s[n]即是所求答案。本题唯一一个值得注意的点就是当n接近60时会爆int。
int main()
{
    int n,i;
    long long s[70],f[70];//s[i]表示i个木桩时的结果,f[i]表示把最后一个木桩放到第i个位置的方案数
    while(cin>>n)
    {
        s[1]=1;
        s[2]=2;
        s[3]=3;
        f[1]=f[2]=f[3]=1;
        for(i=4;i<=n;i++)
        {
            f[i]=s[i-3]+1;
            s[i]=s[i-1]+f[i];
        }
        cout<<s[n]<<endl;
    }
 
 
    return 0;
}


Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts