Top

(ΦωΦ)＜これのつづきですよー。目次はここ。

---
これをやろう。
お寿司が $N$ 皿あります。それぞれが美味しさをパラメータとして持っています。
連続したお皿を取れないというルールがある中で、美味しさの合計を最大にするようにお寿司を取ったとき、その美味しさはいくらになりますか。yukicoder No.45
$N$ は $1{,}000$ 以下。それぞれの美味しさは $100$ 以下。

まずは再帰で全探索を書いてみよう。
求めたいものは何か(戻り値)、それを求めるためには何が必要か(引数)を考えること。

(ΦωΦ)＜解き方1 左からお寿司を取っていった場合
#include <iostream>
#include <algorithm>
using namespace std;

int n;
vector<int> v;

// i番目を取ろうか取るまいか悩んでいる状態。
// この状態でのこれまで(左から取っていったとする)の美味しさの最大値を返す。
int rec(int i) {
  if(i < 0) { return 0; }
  int res = max(rec(i-2) + v[i], rec(i-1));
  return res;
}

int main(void) {
  scanf("%d", &n);
  v.assign(n, 0);
  for(int i=0; i<n; i++) { scanf("%d", &v[i]); }
  int res = max(rec(n-1), rec(n-2));
  printf("%d\n", res);
  return 0;
}

(ΦωΦ)＜解き方2 右からお寿司を取っていった場合
#include <iostream>
#include <algorithm>
using namespace std;

int n;
vector<int> v;

// i番目を取ろうか取るまいか悩んでいる状態。
// この状態でのこれまで(右から取っていったとする)の美味しさの最大値を返す。
int rec(int i) {
  if(i >= n) { return 0; }
  int res = max(rec(i+2) + v[i], rec(i+1));
  return res;
}

int main(void) {
  scanf("%d", &n);
  v.assign(n, 0);
  for(int i=0; i<n; i++) { scanf("%d", &v[i]); }
  int res = max(rec(0), rec(1));
  printf("%d\n", res);
  return 0;
}

---
あとはこれをメモする。

(ΦωΦ)＜解き方1 左から取っていった場合
#include <iostream>
#include <algorithm>
using namespace std;

int n;
vector<int> v, dp;

// i番目を取ろうか取るまいか悩んでいる状態。
// この状態でのこれまで(左から取っていったとする)の美味しさの最大値を返す。
int rec(int i) {
  if(i < 0) { return 0; }
  if(dp[i] > 0) { return dp[i]; }
  int res = max(rec(i-2) + v[i], rec(i-1));
  return dp[i] = res;
}

int main(void) {
  scanf("%d", &n);
  v.assign(n, 0);
  for(int i=0; i<n; i++) { scanf("%d", &v[i]); }
  dp.assign(n, 0);
  int res = max(rec(n-1), rec(n-2));
  printf("%d\n", res);
  return 0;
}

(ΦωΦ)＜解き方2 右から取っていった場合
#include <iostream>
#include <algorithm>
using namespace std;

int n;
vector<int> v, dp;

// i番目を取ろうか取るまいか悩んでいる状態。
// この状態でのこれまで(右から取っていったとする)の美味しさの最大値を返す。
int rec(int i) {
  if(i >= n) { return 0; }
  if(dp[i] > 0) { return dp[i]; }
  int res = max(rec(i+2) + v[i], rec(i+1));
  return dp[i] = res;
}

int main(void) {
  scanf("%d", &n);
  v.assign(n, 0);
  for(int i=0; i<n; i++) { scanf("%d", &v[i]); }
  dp.assign(n, 0);
  int res = max(rec(0), rec(1));
  printf("%d\n", res);
  return 0;
}

(ΦωΦ)＜つづく