paizaラーニング レベルアップ問題集 DPメニュー JavaScript 【最安値】最安値を達成するには 4

【最安値】最安値を達成するには 4 (paizaランク B 相当)

解答例

dpはn以上買うのに、n＋zで十分。最小値を求めるので、初期値は無限大にしておく。
とりあえず、うまく求まらないところを含めてdp[i]の最小値を求める。

うまく求まらなかったところは、dp2を用意して、
dp2[i]に、dpのi以上をsliceして、その中の最小値をreduceで求め、代入していく。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

const [n, x, a, y, b, z, c] = lines[0].split(" ").map(Number);
const dp = Array(n + z).fill(Infinity);//n個買うのにn+z個で十分、最小値を求めるので、初期値は無限大にしておく。
//とりあえず、うまく求まらないところを含めて最小値
dp[0] = 0;
for (let i = 1; i < n + z; i++) {
  if (i >= x) {
    dp[i] = Math.min(dp[i], dp[i - x] + a);
  } 
  if(i >= y){
    dp[i] = Math.min(dp[i], dp[i - y] + b);
  }
  if(i >= z){
    dp[i] = Math.min(dp[i], dp[i - z] + c);
  }
}

const dp2 = Array(n + z);// n 個以上のりんごを買うのに必要な金額の最小値
for (let i = 1; i < n + z; i++) {
  dp2[i] = dp.slice(i, n + z).reduce((a, b) => Math.min(a, b));//i以上で最小値
}
console.log(dp2[n]);

dp2以下を、dp2を無くして、dpを書き換える、以下のようにしてもよい。

// n 個以上のりんごを買うのに必要な金額の最小値
for (let i = 1; i < n + z; i++) {
  dp[i] = dp.slice(i, n + z).reduce((a, b) => Math.min(a, b));//i以上で最小値
}
console.log(dp[n]);

解答例(C++の場合を参考に)

dp2を用意して、
dpのj=i+1からj=n+z-1までのdp[j]と、dp2[i]初期値とを、比較していく。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

const [n, x, a, y, b, z, c] = lines[0].split(" ").map(Number);
const dp = Array(n + z).fill(Infinity);//n個買うのにn+z個で十分、最小値を求めるので、初期値は無限大にしておく。
//とりあえず、うまく求まらないところを含めて最小値
dp[0] = 0;
for (let i = 1; i < n + z; i++) {
  if (i >= x) {
    dp[i] = Math.min(dp[i], dp[i - x] + a);
  } 
  if(i >= y){
    dp[i] = Math.min(dp[i], dp[i - y] + b);
  }
  if(i >= z){
    dp[i] = Math.min(dp[i], dp[i - z] + c);
  }
}

const dp2 = Array(n + z);// n 個以上のりんごを買うのに必要な金額の最小値
for(let i = n+z-1; i >= 1; i--){ //dpの後ろから
  dp2[i] = dp[i];//初期値代入して
  //dpのj=i+1からj=n+z-1までのdp[j]と、dp2[i]初期値とを、比較していく。
  for(int j = i+1; j < n+z; j++){
    dp2[i] = Math.min(dp2[i], dp[j]);
  }
}
console.log(dp2[n]);

解答例(Python3の場合を参考に)

スライスを利用して、n 個以上のりんごを買うのに必要な金額の最小値を求めることもできます。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

const [n, x, a, y, b, z, c] = lines[0].split(" ").map(Number);
const dp = Array(n + z).fill(Infinity);//n個買うのにn+z個で十分、最小値を求めるので、初期値は無限大にしておく。
//とりあえず、うまく求まらないところを含めて最小値
dp[0] = 0;
for (let i = 1; i < n + z; i++) {
  if (i >= x) {
    dp[i] = Math.min(dp[i], dp[i - x] + a);
  } 
  if(i >= y){
    dp[i] = Math.min(dp[i], dp[i - y] + b);
  }
  if(i >= z){
    dp[i] = Math.min(dp[i], dp[i - z] + c);
  }
}
//スライスを利用して、n 個以上のりんごを買うのに必要な金額の最小値を求める
console.log(dp.slice(n).reduce((a, b) => Math.min(a, b)));

解答例(Javaの場合、C++の場合の別解を参考)

dpの後ろから、最小値を変換していく。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

const [n, x, a, y, b, z, c] = lines[0].split(" ").map(Number);
const dp = Array(n + z).fill(Infinity);//n個買うのにn+z個で十分、最小値を求めるので、初期値は無限大にしておく。
//とりあえず、うまく求まらないところを含めて最小値
dp[0] = 0;
for (let i = 1; i < n + z; i++) {
  if (i >= x) {
    dp[i] = Math.min(dp[i], dp[i - x] + a);
  } 
  if(i >= y){
    dp[i] = Math.min(dp[i], dp[i - y] + b);
  }
  if(i >= z){
    dp[i] = Math.min(dp[i], dp[i - z] + c);
  }
}
//dpの後ろから、最小値を変換していく。
for (int i = n + z - 2; i >= 1; i--) { 
  dp[i] = Math.min(dp[i], dp[i + 1]);
}
console.log(dp[n]);