長さ $1$ から $30$ の中から,$3$ 種類の長さを選び,その長さの板をいくらでも手に入れることができるようになる.
板は繋げることはできても,切ることはできない.
長さ $V_0, V_1, V_2, V_3$ の板をそれぞれ $1$ つずつ作りたい場合,必要な板の数の最小値はいくらになるかを求める問題.
$3$ 種類の長さの選び方は約 $30^3 / 3!$ 通り全て試す.
使える板の長さを決めた時,それぞれ長さ $k$ の板を作るための必要な板の最小枚数 $\verb|dp[|k\verb|]|$ をDPで求める.
使える長さが $a,b,c$ だとすると,$\verb|dp[|k\verb|]| = \min (\verb|dp[|k-a\verb|]|, \verb|dp[|k-b\verb|]|, \verb|dp[|k-c\verb|]|) + 1$ で計算できる.
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define INF 100000
int V[4];
int dp[1000];
int main(){
int i, j, k, n=4;
int res = INF, tmp;
int a[3];
rep(i,n) scanf("%d",V+i);
REP(a[0],1,31) REP(a[1],a[0]+1,31) REP(a[2],a[1]+1,31){
rep(i,35) dp[i] = INF;
dp[0] = 0;
rep(k,3) REP(i,a[k],35) dp[i] = min(dp[i], dp[i-a[k]]+1);
tmp = 0;
rep(i,n) tmp += dp[V[i]];
res = min(res, tmp);
}
printf("%d\n",res);
return 0;
}
Current time: 2024年03月29日15時29分25秒
Last modified: 2014年11月06日13時03分53秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る
Logged in as: unknown user (not login)