Problem 1011 : Finding the Largest Carbon Compound Given Its Long

AOJ v10 会津大学オリジナル問題

Problem C: Finding the Largest Carbon Compound Given Its Longest Chain
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1011

  • 問題概要

４つまでエッジを持てるノードのグラフを考える。ノード間の最大の距離が与えられた数字以内のグラフをつくるとき、一番大きな（ノードの数がおおい）グラフを求めよ、そのノードの数をだせ

  • 解法

とりあえず、手で書いてみるとDPできることがわかる。
(1) ｎが奇数の時
t[n] = t[n-1] + t[n-1] + 1
→t[n-1]*2 + 1
(2) nが偶数の時
t[n] = t[n-1] + t[n-2] + 1

になる。法則をみつける

  • ソース
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<sstream>
#include<cassert>
#include<queue>
#include<stack>

#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define pb         push_back
#define mp         make_pair
#define vint       vector<int>
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)
#define lli	    long long int
#define ld	    long double

using namespace std;


main(){
  int t[32];
  t[0] = 0;
  REP(i, 1, 31){
    if( i % 2 == 1)t[i] = t[i-1] * 2 + 1;
    if( i % 2 == 0)t[i] = t[i-1] + t[i-2] + 1;
  }
  int n;
  while(cin >> n)cout << t[n] << endl;
}

楽しかった！おもしろい問題！！