CFR 366 C. Dima and Salad ( Diff DP )

Problem - C - Codeforces

題意：
給 A, B 陣列，求一組序列 { i1, i2, .. } 滿足 SIGMA{ A[ i ] } / SIGMA{ B[ i ] } = K。在此前提下，求 SIGMA{ A[ i ] } 的最大值。若無解則輸出 -1。

數據範圍：
陣列大小 1 ≤ N ≤ 100
比例 1 ≤ K ≤ 10
陣列元素大小 1 ≤ A[ i ], B[ i ] ≤ 100

解法：
移一下等式發現，將 B 所有元素乘上 K 後，問題等價於滿足 SIGMA{ A[ i ] } = SIGMA{ B[ i ] }。因此動態規劃可以用差來表示狀態。
dp[ i ][ j ] : 已考慮前 i 個下標，目前所挑選的序列中使得 SIGMA{ A } - SIGMA{ B }，此狀態的最大可能 SIGMA{ A }。
答案便是 dp[ N ][ 0 ]。

時間 / 空間複雜度：
O( N ^ 2 )

int N, K;
vi A;
vi B;

void init(){
    cin >> N >> K;
    A = B = vi( N );
    for( int i = 0; i < N; ++i )
        cin >> A[ i ];
    for( int i = 0; i < N; ++i )
        cin >> B[ i ];
}

vvi dp;
const int offset = ( int ) 1e4;
const int zero = 2 * offset;

void preprocess(){
    for( int i = 0; i < N; ++i )
        B[ i ] *= K;
    dp = vvi( N + 1, vi( offset * 4, -INF ) );
    dp[ 0 ][ zero ] = 0;
    for( int i = 0; i < N; ++i )
        for( int d = zero - offset; d <= zero + offset; ++d )
            upmax( dp[ i + 1 ][ d ], dp[ i ][ d ] ),
            upmax( dp[ i + 1 ][ d + A[ i ] - B[ i ] ], dp[ i ][ d ] + A[ i ] );
}

void solve(){
    if( dp[ N ][ zero ] == 0 )
        cout << -1 << endl;
    else
        cout << dp[ N ][ zero ] << endl;
}