naoya_t@topcoder

SRM363 Div1 Easy: HandsShaking

過去問, 練習 | 00:51 |

ちょっと悩んだ。203.42点(=14'17")

• DP。最初の１人が誰と手をつなぐか。その線の右側と左側の小グループについて考える分割統治。
• 最初の１人は、右側と左側の小グループにそれぞれ偶数人が属するように相手を選んで手をつなぐ。というか、隣りの人から始めて１人おきに回り、反対側の隣りの人で終わる。

typedef long long ll;
#define found(s,e)  ((s).find(e)!=(s).end())

class HandsShaking {
  map<int,ll> memo;
 public:
  long long countPerfect(int n) {
    if(n==0) return 0LL;
    if(n==2) return 1LL;
    if(found(memo,n)) return memo[n];
    ll sum=0;
    for(int i=1;i<n;i+=2){
      int a=i-1, b=n-i-1;
      if(a==0) sum+=countPerfect(b);
      else if(b==0) sum+=countPerfect(a);
      else sum+=countPerfect(a)*countPerfect(b);
    }
    return memo[n]=sum;
  }
};