CFR 626 F. Group Projects ( Segment Trick DP )

Problem - F - Codeforces
題意：
給 N, K，代表有多少學生，以及花費總和上限。接著給學生們的實力 A。現在把學生分組，一組的花費是最大實力和最小實力的差。求花費不超過 K，將所有學生分組的方案數，求其餘數。
解法：
先將學生按實力排序後，定義動態規劃。
dp[ i ][ j ][ k ] : 已將前 i 個學生分組完，目前有 j 個至少還要再加入一個學生的群組，目前花費為 k 的方案數。
會發現，考慮完目前這個學生 i 後，每個需要再加入一個學生的群組花費上升的量一定都是 A[ i ] - A[ i - 1 ]。因為就算某個組沒有要加入他，那個組必定要加入更大的某個實力值，所以可以考慮成一段一段將中間的差加入，會是同樣效果。因此轉移就很容易：
dp[ i + 1 ][ j ][ k + j * ( A[ i ] - A[ i - 1 ] ) ] += dp[ i ][ j ][ k ] :

• 將目前這位學生獨立放成一組，從此不再理他。

dp[ i + 1 ][ j + 1 ][ k + j * ( A[ i ] - A[ i - 1 ] ) ] += dp[ i ][ j ][ k ] :

• 將目前這位學生暫時獨立放成一組，約定這個組至少還要再加一個

dp[ i + 1 ][ j ][ k + j * ( A[ i ] - A[ i - 1 ] ) ] += j * dp[ i ][ j ][ k ] :

• 將目前這位學生插入任意一組，並仍然約定該組至少還要再加一個

dp[ i + 1 ][ j - 1 ][ k + j * ( A[ i ] - A[ i - 1 ] ) ] += j * dp[ i ][ j ][ k ] :

• 將目前這位學生插入任意一組，並約定這個組不會再收人

int N, K;
vi A;

void init(){
    cin >> N >> K;
    A = vi( N );
    for( int i = 0; i < N; ++i )
        cin >> A[ i ];
    sort( A.begin(), A.end() );
}

vvvi dp;

void preprocess(){
    dp = vvvi( N + 1, vvi( N + 1, vi( K + 1 ) ) );
    dp[ 0 ][ 0 ][ 0 ] = 1;
    for( int i = 0; i < N; ++i )
        for( int j = 0; j <= N; ++j )
            for( int k = 0; k <= K; ++k ){
                int nk = i == 0 ? 0 : k + j * ( A[ i ] - A[ i - 1 ] );
                if( K < nk ) continue;
                ( dp[ i + 1 ][ j ][ nk ] += dp[ i ][ j ][ k ] ) %= MOD7; // open a group and immediately close it
                if( j + 1 <= N )
                    ( dp[ i + 1 ][ j + 1 ][ nk ] += dp[ i ][ j ][ k ] ) %= MOD7; // open a group and leave it open
                ( dp[ i + 1 ][ j ][ nk ] += 1LL * j * dp[ i ][ j ][ k ] % MOD7 ) %= MOD7; // choose a group and insert, and leave it open
                if( 0 <= j - 1 )
                    ( dp[ i + 1 ][ j - 1 ][ nk ] += 1LL * j * dp[ i ][ j ][ k ] % MOD7 ) %= MOD7; // choose a group and insert, and close it
            }
}

void solve(){
    int ans = 0;
    for( int i = 0; i <= K; ++i )
        ( ans += dp[ N ][ 0 ][ i ] ) %= MOD7;
    cout << ( ans + MOD7 ) % MOD7 << endl;
}