Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-05-12

[][] Project Euler Problem 77 01:01 はてなブックマーク -  Project Euler Problem 77 - 練習帳

問題文

 http://projecteuler.net/index.php?section=problems&id=77

要約

 不定数の素数の和で表す表し方が5000通りを超えるもののうち,最小の整数を答えよ.(例えば 和が10となる足し方は次の 5 通り )

10 = 7 + 3
          5 + 5
          5 + 3 + 2
          3 + 3 + 2 + 2
          2 + 2 + 2 + 2 + 2

方針

 一番最後に追加した数と残りの合計で動的計画法をおこなう.

コード例(C++)

#include <iostream>
#include <map>
#include <utility>
#include <algorithm>

using namespace std;

map<pair<int, int> ,int> table;
typedef map<pair<int, int> ,int> ::const_iterator ittype;

int N = 5000;

bool isprime(int n){
  if(n == 0 || n == 1) return false;
  for(int i = 2; i * i <= n; i++){
    if(n % i == 0)
      return false;
  }
  return true;
}

int dp(int top, int sum){
  if(sum < 0 ) return 0;
  if(sum == 0 ) return 1;
  if(table.count(make_pair(top, sum)) > 0 ) 
    return table[make_pair(top, sum)];
  int ans = 0;
  for(int i = 0; i <= top; i++){
    if(!isprime(i)) continue;
    ans += dp(i, sum-i);
  }
  return table[make_pair(top, sum)] = ans;
}

int main(){  
  for(int i = 0 ;;i++){
    if(dp(i, i) > N){
      cout << i << " " << dp(i, i) << endl;
      return 0;
    }
  }
  return 0;
}