yukicoder No.27 - 板の準備

Source

ニコニコミュニティ
問題文

問題概要

長さ $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$ で計算できる.

C++によるスパゲッティなソースコード

#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)

ログイン: