白駿7579-AppC++

11486 ワード
アルゴリズム#アルゴリズム# C テキストリンク
質問リンク

質問する



に答える


これは肉色の問題と似たような問題だ.
似たような方法で解答したが、最後に思いがけないミスが出たので、他の記事を参考にした.
与えられたメモリは10000,00なので、メモリに基づいてDPアレイを作成するとタイムアウトすると思います.
そこで,費用を基準としてDP案を策定した.
だから点火式は、
 DP[j] = max(DP[j], DP[j - c[i]] + m[i]);
はい.
アレイストレージは、所定のコストで最大どれだけのメモリを使用できますか.
エラーの部分は,DPを行う過程で,誤って実行順序が指定されている.
void calcDP(){
    for(int i = 0; i < N; i++){
        for(int j = c[i]; j < COST_LIMIT; j++){
            DP[j] = max(DP[j], DP[j - c[i]] + m[i]);
        }
    }
}
最初は上記のようにjが増加するように公式を構築し,これにより,繰り返し文のループに伴って更新されたDP[j]が以降の再計算に用いられる.
そこで,DPを減らす方向に数式を構築し,一度だけ計算できるように修正した.

最終コード

#include <iostream>
#include <algorithm>
#define COST_LIMIT 10001

using namespace std;

int N, M;
int m[100];
int c[100];
int DP[COST_LIMIT];

void input(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;

    for(int i = 0; i < N; i++){
        cin >> m[i];
    }

    for(int i = 0; i < N; i++){
        cin >> c[i];
    }
}

void calcDP(){
    for(int i = 0; i < N; i++){
        for(int j = COST_LIMIT - 1; j >= c[i]; j--){
            DP[j] = max(DP[j], DP[j - c[i]] + m[i]);
        }
    }
}

void findAns(int require_mem){
    for(int i = 0; i < COST_LIMIT; i++){
        if(DP[i] >= require_mem){
            cout << i;
            return;
        }
    }
}

int main(){
    input();

    calcDP();

    findAns(M);

    return 0;
}
スパルタコードクラブ-反応5週間(7)
[マルコの学習ログ]ページ開発総合クラス第2週後期(3)