#139848 (C++11) No.27 板の準備

• 問題: No.27 板の準備
• ユーザー: koba-e964
• 提出日時: 2016-12-19 11:57:50
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 7 ms / 5,000 ms
• コード長: 753 bytes
• コンパイル時間: 519 ms
• コンパイル使用メモリ: 62,844 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-06-08 00:34:43
• 合計ジャッジ時間: 1,437 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	6 ms; 5,248 KB
testcase_01	AC	6 ms; 5,376 KB
testcase_02	AC	5 ms; 5,376 KB
testcase_03	AC	5 ms; 5,376 KB
testcase_04	AC	7 ms; 5,376 KB
testcase_05	AC	6 ms; 5,376 KB
testcase_06	AC	6 ms; 5,376 KB
testcase_07	AC	6 ms; 5,376 KB
testcase_08	AC	6 ms; 5,376 KB
testcase_09	AC	6 ms; 5,376 KB
testcase_10	AC	6 ms; 5,376 KB
testcase_11	AC	6 ms; 5,376 KB
testcase_12	AC	6 ms; 5,376 KB
testcase_13	AC	6 ms; 5,376 KB
testcase_14	AC	6 ms; 5,376 KB
testcase_15	AC	6 ms; 5,376 KB
testcase_16	AC	6 ms; 5,376 KB
testcase_17	AC	6 ms; 5,376 KB

ソースコード

#include <algorithm>
#include <bitset>
#include <cassert>
#include <iostream>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

using namespace std;
typedef vector<int> VI;


int knapsack(VI &t, int val) {
  int n = t.size();
  int B = 40;
  VI dp(B, 10000);
  dp[0] = 0;
  REP(i, 0, n) {
    REP(j, 0, B) {
      if (j >= t[i]) {
	dp[j] = min(dp[j], dp[j - t[i]] + 1);
      }
    }
  }
  return dp[val];
}

int main(void){
  VI v(4);
  int mi = 0;
  REP(i, 0, 4) { cin >> v[i]; mi += v[i]; }
  REP(a, 0, 31) {
    REP(b, a + 1, 31) {
      REP(c, b + 1, 31) {
	int sum = 0;
	VI t(3);
	t[0] = a;
	t[1] = b;
	t[2] = c;
	REP(i, 0, 4) {
	  sum += knapsack(t, v[i]);
	}
	mi = min(mi, sum);
      }
    }
  }
  cout << mi << endl;
}