Problem Solving►UVa

UVa 11069 - A Graph Problem

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址
中文網址

找出 n 內有幾個集合，符合規則。

  1. 數字不能相鄰
  2. 維持 1 ，且不能再加入任何點了

Solution

n 時，有兩種情況:

  1. 集合內有 n :
    (n-2) 集合內元素再加上 n

  2. 集合內沒有 n :
    (n-3) 集合內的元素再加上 n-1

也可觀察一下規律，得出:

dp[2] = dp[3] = 2
dp[1] = 1
dp[n] = dp[n-2] + dp[n-3]

Code

UVa 11069UVa 11069 - A Graph Problem
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#include<cstdio>

int main()
{
    int dp[77] = {0,1,2,2};
    for (int i = 4; i < 77; i++)
        dp[i] = dp[i - 2] + dp[i - 3];

    int n;
    while (scanf("%d", &n) != EOF)
        printf("%d\n", dp[n]);

    return 0;
}