Yuki 412 花火大会 ( DP )
題意:
有三個人分別要 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; }