UVa 11069 A Graph Problem (斐波那契)

 A Graph Problem 

Time limit: 2s

Given an undirected graph of the following form with n nodes, 1 ≤ n ≤ 76: 

 

Your task is to calculate the number of subsets of nodes of the graph with the following properties:

no nodes in the subset should be connectedit shouldn't be possible to add further nodes to the subset without violating the first conditionFor a graph with 5 nodes the number of subsets which fulfill the above conditions is 4. The subsets are {1,3,5},{2,4},{2,5},{1,4}.

Input

The input will consist of a sequence of numbers n,1 ≤ n ≤ 76. Each number will be on a separate line. The input will be terminated by EOF.

Output

Output the number of subsets as described above on a single line. The number of all subsets will be less than 2^31.

Sample input

1234530

Sample output

122344410

题意：找子集个数， 子集必须满足 元素之差在2-3之间。


思路：dp，对于第i个元素而言，他可以与他的i-2和i-3元素构成的集合在构成集合，所以dp[i] = dp[i-2] + dp[i - 3];


代码：


#include <stdio.h>#include <string.h>int n, dp[77];int main() {    dp[0] = dp[1] = 1; dp[2] = 2;    for (int i = 3; i <= 76; i ++) {dp[i] = dp[i - 3] + dp[i - 2];    }    while (~scanf("%d", &n)) {printf("%d\n", dp[n]);    }    return 0;}