😺

ABC204 D-Cooking(C++)

2023/01/04に公開約1,700字

問題概要

問題文

料理1からNN品の料理を作る。
料理iは、オーブンを連続してT_i分間使うことで作れる。1つのオーブンを2つ以上の料理のために同時に使うことはできない。
2つのオーブンを使えるとき、N品の料理を全て作るまでに最短で何分かかるか?

制約

  • 1\leq N\leq 100
  • 1\leq T_i\leq 10^3
  • 入力はすべて整数

問題リンク

解法

言い換えると、次の通り。

  • \{1,2,\dots,N\}=X \cup Yと分割する
  • \max(\sum_{i\in X}{T_i},\sum_{i\in Y}{T_i})を最小化せよ。

以下S_X=\sum_{i\in X}{T_i},S_Y=\sum_{i\in Y}{T_i},S=\sum_{i=1}^{N}{T_i}とします。


この問題の重要なポイントとして、X,Yについて、知りたいのはそれぞれS_X,S_Yのみということがあります。これは、最小化する式がS_X,S_Yのみで表されるからです。
もっと言うと、S_Y=S-S_Xなので、S_Xが分かればS_Yも自動的にわかります。したがって、S_Xを決め打って調べていこうという方針が立ちます。
S_Xに対応するXがそもそも存在しないかもしれないということに注意しましょう。これは、部分和問題の要領で解決できます。


まとめると、次のようにすればいいです。

  • あらかじめ、Tについての部分和問題を解いておく。
  • S_X=0,1,\dots,Sに対して、以下を繰り返す
    • 対応するXが存在しなければスキップ
    • S_Y=S-S_Xについて、ans=\min(ans,\max(S_X,S_Y))と更新する

実装

計算量O(NS)です。

main.cpp
#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int> t(n);
    for(int i=0;i<n;i++)cin>>t[i];
    int S=0;
    for(int i=0;i<n;i++)S+=t[i];
    //部分和問題を解いておく
    //dp[i][j]:=先頭i項をみる。いくつか選んで和をjにできるか?
    vector<vector<bool>> dp(n+1,vector<bool>(S+1,false));
    dp[0][0]=true;
    for(int i=0;i<n;i++)for(int j=0;j<=S;j++){
        if(!dp[i][j])continue;  //dp[i][j]=falseなら、dp[i][j]からの遷移は起きない

        dp[i+1][j]=true;    //t_iを選ばない場合
        dp[i+1][j+t[i]]=true;   //選ぶ場合
    }
    const int inf=1e9;
    int ans=inf;
    for(int sx=0;sx<=S;sx++){
        if(!dp[n][sx])continue; //作れないならcontinue
        int sy=S-sx;
        int time=max(sx,sy);    //全体でかかる時間
        ans=min(ans,time);
    }
    cout<<ans<<endl;
}

Discussion

ログインするとコメントできます