Yuki 412 花火大会 ( DP )

No.412 花火大会 - yukicoder

題意：
有三個人分別要 R[ 0 ], R[ 1 ], R[ 2 ] 以上面積的一塊布料。現在有若干個布料，求有多少種帶布料的方法，能滿足三個人的需要。

資料規模：
布料數 1≤N≤30
布料大小 1≤Ei≤100
時限 2000 ms
記憶體 512 MB

解法：
想省去討論組合重複的情況，可以試試看排序後產生的單調性。
對需求和布料分別依面積升序排序後，考慮
dp[ i ][ j ] : 已考慮前 i 個布料，滿足了前 j 個需求
由於單調性和貪婪的正確性，這麼算一定不會重複或漏算組合。
貪婪的部分在於，對升序排序過的三個布料 ( x, y, z ) 和升序排序過的三個需求 ( a, b, c )，如果是可行的方案，那麼 x 分配給 a，y 分配給 b，z 分配給 c，一定是沒有問題的，因此不會漏算。也因為排序後不會再變動順序，這個布料的組合不會被重複算到。

時間 / 空間複雜度：
O( | R | * | E | )

vi R;
int N;
vi E;

void init(){
  R = vi( 3 );
  for( int i = 0; i < 3; ++i )
    cin >> R[ i ];
  cin >> N;
  E = vi( N );
  for( int i = 0; i < N; ++i )
    cin >> E[ i ];
}

int dp[ 30 + 1 ][ 3 + 1 ];

void preprocess(){
  sort( R.begin(), R.end() );
  sort( E.begin(), E.end() );
  dp[ 0 ][ 0 ] = 1;
  for( int i = 0; i < N; ++i )
    for( int j = 0; j <= 3; ++j ){
      dp[ i + 1 ][ j ] += dp[ i ][ j ]; // not take
      // take
      if( j == 3 or R[ j ] > E[ i ] )
        dp[ i + 1 ][ j ] += dp[ i ][ j ];
      else{
        dp[ i + 1 ][ j + 1 ] += dp[ i ][ j ];
      }
    }
}

void solve(){
  cout << dp[ N ][ 3 ] << endl;
}