(ΦωΦ)<これの答えですよー。目次はここ。
---
問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;
}
(ΦωΦ)<おしまい