白駿2073水道工事

問題の説明

問題へのアクセスは,特定の値を構築するためにどのように異なるタイプの重み付けを用いて異なるタイプの選択を構築し,最大限の重み付けで構築すればよいのか,DPではKnapsack方式を用いて解くことも可能である.ただし、問題で厳しい部分が要求された場合、簡単に「選択したタイプ」*「構成する重み値」の配列でDPを宣言すると、メモリが過剰になります.

メモリが140 MBを超える!
したがって,メモリを効率的に使用してDPにアクセスする方法が必要であり,この考えは以前に解いた白駿9084硬貨題から得ることができる.前の種類から得られた値はいずれも次の種類で使用されるので、必ずしも種類の個数で行を宣言するのではなく、最初の円でDPを宣言し、選択地としての種類数を順番に更新する方式でアクセスする.
しかし、同じ方式でも今回の問題とは異なり、コイン問題では1種類のコインを何度も繰り返し使用することができますが、今回の問題では、1回の水道管しか使用できません.このような場合に発生する問題は、今回チェックする水道管を入れるかどうかを決めるが、繰り返すかどうかは分からないことである.
3インチの水道管を置くかどうかを決めるとき
1、2の値は長さより小さいのでskip、3のマイナス記号は0、dp[0]が適切な場合は可能に設定します.
このようにすると、問題は後で長さ6で検査を行う場合、3の3の値を外すことが可能であるため、6もこの値に基づいて判断することができる.実は、3は自分を入れているので、不可能な場合です.
この問題を解決するために、通常、前の状態dp値と現在の状態dp値とを分離し、2つの1次元DPを使用してアクセスすることができる.
例の説明
今回はラッキーなことに、少し違う方法でアクセスしましたので、小さな値からインデックスを開始するのではなく、大きな値からインデックスを開始して、現在使用されていない状況だけをチェックするように紹介します.最初のDPまで更新して使用するため、1つのクラスを開始する前に受信した初期DP値は、以前のクラスで可能な値を保存する.したがって,以前の問題,すなわち自分以外に構成可能な数字に自分の値を加えてこそ検査が可能であるという問題を解決することができる.
なお、前述の例を見ると、6から3を減算し、現在は構成されていない値であるため不可能であり、3から3を減算するので、DP値の更新が可能であると考えられる.
非常に簡単なアイデアを駆使して、DPを1つ並べば問題を解くことができます.

C++コード

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
using pii = pair <ll, ll>;
 
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
  //freopen("inp.txt", "r", stdin);

  int D, P;
  cin >> D >> P;

  vector<int> dp(D+1, 0);
  dp[0] = 1;

  // Kanpsack + 2to1DP
  for(int i=1; i<=P; i++){
    int L, C;
    cin >> L >> C;
    
    // 인덱싱 큰 쪽에서부터 내려와야 하나의 파이프라인 중복적으로 사용 안 할 수 있음
    for(int j=D; j>=L; j--){
      if(dp[j-L]){
        if(j==L) 
          dp[j] = max(dp[j], C);
        else
          dp[j] = max(min(dp[j-L], C), dp[j]);
      }
    }
  }
  cout << dp[D];
}