PKU 3132 Sum of Different Primes

問題

Sum of Different Primes

解法

動的計画法の勉強。DPどうやって書くのか、検討つかん。諦めてDFSで書いてみた。引数、３つになる。減らそうと思ったけど減らせない。O(1120以下の素数の数\K\N)で実装できそうだと思ったけど、O(K\N)*の実装考えてた。

制約確認して3重ループで間に合うじゃん。

心臓に悪いコード

DFS(地球を爆発させる諸悪の根源)

// 残り何個の素数を使うか, 合計の数字, c個目までの素数
int dfs(int i, int j, int c){
  int res = 0;
  if(i == 0 && j == n) res = 1;
  else if(i > 0 && j < n && c < p.size()) res = dfs(i-1, j+p[c], c+1) + dfs(i, j, c+1);
  return res;
}

DP

int dp[MAX_K+1][MAX_N+1];
int n, k, tp[MAX_N];
vector<int>p;

int main(){
  tp[0] = tp[1] = 1;
  REP(i, 2, MAX_N/2){
    if(tp[i]) continue;
    for(int j = i+i; j < MAX_N; j+=i) tp[j] = 1;
  }

  rep(i, MAX_N) if(!tp[i]) p.PB(i);

  dp[0][0] = 1;
  for(int i = 0; i < p.size(); i++){
    for(int j = MAX_K - 1; j >= 0; j--){
      rep(l, MAX_N){
    if(l + p[i] > MAX_N) continue;
    dp[j+1][l+p[i]] += dp[j][l];
      }
    }
  }

  while(scanf("%d%d", &n, &k) && n+k)
    printf("%d\n", dp[k][n]);

  return 0;
}

ループの順番で迷って、さらにループの向きで迷った。 jのループを0から始めると同じ素数を複数回選択してしまう。