Algoogle

Algorithm for Programming Contest

AOJ 2576 Doctor Course Is Recommended

Category: AOJ Tag: dp

Doctor Course Is Recommended

問題概要


D個のマスに’D’とマークすることが許される.
マスが1個の問題とマスが2個の問題がいくつかあり, それぞれに配点が決まっている.
このとき得られる得点の最大値はいくらか.

解法


dp[i] := マークがi個以下の時の得点の最大値
で答えがD(もしくはDD)の問題が見つかるたびに更新すればよい.
更新はiが大きい方からやること

####


(2576.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i,a) repi(i,0,a)
int D, N, sc, dp[16];
string s;

int main(){
    cin >> D;
    rep(i,2){
        cin >> N;
        while(N--){
            cin >> s >> sc;
            if(s == "D" or s == "DD")
                for(int j = D-i-1; j >= 0; j--)
                    dp[j+i+1] = max(dp[j+i+1], dp[j]+sc);
        }
    }
    cout << dp[D] << endl;
    return 0;
}

Comments