D - 高橋くんの苦悩

時間制限 : 2sec / メモリ制限 : 256MB

問題文

高橋くんは、ソフトウエアが期待通りに動いたというエビデンス（証拠）として、画面のスクリーンショットを表計算ソフトに貼り付ける作業を命じられました。画面のスクリーンショットは N 枚あり、高さは全て等しいのですが、幅が異なります。また、表計算ソフトに貼りつけ可能なスクリーンショットには 2 つの制約が存在します。

表計算ソフトの幅は W しかない。そのため、貼りつけるスクリーンショットの幅の合計値は W 以下でなければならない。表計算ソフトは K 枚より多くのスクリーンショットを貼りつけることが出来ない。よって、表計算ソフトに貼りつけ可能なスクリーンショットは K 枚までである。さらに、スクリーンショットには「重要度」が存在するため、高橋くんは 2 つの制約を満たしながら、貼り付けるスクリーンショットが持つ重要度の合計値を最大化したいです。しかし、彼にとってこの仕事は難しいので、あなたが彼の代わりに表計算ソフトに貼り付け可能なスクリーンショットが持つ重要度の合計の最大値を求めてください。

Note

動的計画法で次元削減すれば解けるお O(n_k_w) で10**7くらい

#include <iostream>
#include <vector>
using namespace std;

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int main(){
    int w, n, k;
    cin >> w;
    cin >> n >> k;
    int weight[51];
    int value[51];

    for (int i = 0; i < n; ++i)
    {
        cin >> weight[i] >> value[i];
    }

    int dp[10010][52]; // 次元削減 重さと何
    Fill(dp, 0);
    int dp2[10010][52];
    Fill(dp2, 0);

    for (int i = 0; i < n; ++i)
    {
        for (int j = w; j >= 0; --j)
        {
            for (int s = k; s >= 0; --s)
            {
                dp2[j][s] = dp[j][s];
                if(j + weight[i] <= w &&  dp2[j + weight[i]][s+1] <  dp2[j][s] + value[i]){
                    dp2[j + weight[i]][s+1] = dp2[j][s] + value[i];
                }
            }
        }

        for (int j = 0; j <= w; ++j)
        {
            for (int s = 0; s <= k ; ++s)
            {
                dp[j][s] = dp2[j][s];
                dp2[j][s] = 0;
            }
        }
    }

    cout << dp[w][k] << endl;

}

TakefumiYamamura / programming_contest

AtCoder Beginner Contest 015 #29

D - 高橋くんの苦悩

問題文

Note