Top

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

---
問1-4
#include <iostream>
#include <algorithm>
using namespace std;

class MutaliskEasy { public: int minimalAttacks(vector<int> x); };

const int inf = 987654321;
vector<vector<vector<int>>> dp;

int f(int x, int d) { return max(0, x-d); }

// 敵3体のHPをvectorにまとめたものを引数にする。
// dp[1体めの残りHP][2体めの残りHP][3体めの残りHP] = 何ターンかかる
int rec(vector<int> a) {
  sort(a.begin(), a.end());
  int x = a[0], y = a[1], z = a[2];
  if(x == 0 && y == 0 && z == 0) { return 0; }
  if(dp[x][y][z] > 0) { return dp[x][y][z]; }
  vector<int> v = {1, 3, 9};
  int res = inf;
  do {
    res = min(res, rec({f(x,v[0]), f(y,v[1]), f(z,v[2])}) + 1);
  } while(next_permutation(v.begin(), v.end()));
  return dp[x][y][z] = res;
}

int MutaliskEasy::
minimalAttacks(vector<int> a) {
  int n = a.size();
  for(int i=n; i<3; i++) { a.push_back(0); }
  dp.assign(70, vector<vector<int>>(70, vector<int>(70, 0)));
  int res = rec(a);
  return res;
}
    

(ΦωΦ)<6通りぐらいだったらnext_permutationを使うまでもないかもしれない。
#include <iostream>
#include <algorithm>
using namespace std;

class MutaliskEasy { public: int minimalAttacks(vector<int> x); };

const int inf = 987654321;
vector<vector<vector<int>>> dp;

int f(int x, int d) { return max(0, x-d); }

int rec(vector<int> a) {
  sort(a.begin(), a.end());
  int x = a[0], y = a[1], z = a[2];
  if(x == 0 && y == 0 && z == 0) { return 0; }
  if(dp[x][y][z] > 0) { return dp[x][y][z]; }
  int res = min({rec({f(x,1), f(y,3), f(z,9)}),
                 rec({f(x,1), f(y,9), f(z,3)}),
                 rec({f(x,3), f(y,1), f(z,9)}),
                 rec({f(x,3), f(y,9), f(z,1)}),
                 rec({f(x,9), f(y,1), f(z,3)}),
                 rec({f(x,9), f(y,3), f(z,1)})}) + 1;
  return dp[x][y][z] = res;
}

int MutaliskEasy::
minimalAttacks(vector<int> a) {
  int n = a.size();
  for(int i=n; i<3; i++) { a.push_back(0); }
  dp.assign(70, vector<vector<int>>(70, vector<int>(70, 0)));
  int res = rec(a);
  return res;
}
    

(ΦωΦ)<おしまい