Top

(ΦωΦ)＜これの答えですよー。目次はここ。

---
問2-4
解き方 その1
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 10010;

int main(void) {
  int n; scanf("%d", &n);
  vector<int> p(n);
  vector<vector<bool>> dp(n+1, vector<bool>(N));
  for(int i=0; i<n; i++) { scanf("%d", &p[i]); }
  dp[0][0] = true;
  for(int i=0; i<n; i++) {
    for(int j=0; j<N; j++) {
      if(dp[i][j]) {
        dp[i+1][j] = true;
        dp[i+1][j+p[i]] = true;
      }
    }
  }
  int res = 0;
  for(int j=0; j<N; j++) {
    if(dp[n][j]) { res++; }
  }
  printf("%d\n", res);
  return 0;
}

解き方 その2
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 10010;

int main(void) {
  int n; scanf("%d", &n);
  vector<int> p(n);
  vector<bool> dp(N, false);
  for(int i=0; i<n; i++) { scanf("%d", &p[i]); }
  dp[0] = true;
  for(int i=0; i<n; i++) {
    for(int j=N-1; j>=0; j--) {
      if(dp[j]) { dp[j+p[i]] = true; }
    }
  }
  int res = 0;
  for(int j=0; j<N; j++) {
    if(dp[j]) { res++; }
  }
  printf("%d\n", res);
  return 0;
}

(ΦωΦ)＜おしまい