vs Darmanitan

2 secs 1024 MB

dyktr_06

Problem

Submissions

Test cases

Editorial

以下にような動的計画法を考えましょう。

$dp[i]:$ 体力を $i$ だけ減らした時の攻撃回数の最小値

$i \leq \displaystyle \lfloor \frac{H}{2} \rfloor$ の場合は遷移を行わないことに注意してください。

実装例(C++)

#include<bits/stdc++.h>
using namespace std;

const int INF = 1 << 30;

int dp[10001];

int main(){
    int h, n; cin >> h >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }

    for(int i = 0; i < 10001; i++){
        dp[i] = INF;
    }
    dp[0] = 0;
    for(int i = 0; i < h / 2; i++){
        for(int j = 0; j < n; j++){
            if(dp[i] == INF) continue;
            dp[min(i + a[j], h)] = min(dp[min(i + a[j], h)], dp[i] + 1);
        }
    }

    sort(a.rbegin(), a.rend());
    int ans = INF;
    for(int i = 0; i < h / 2; i++){
        if(dp[i] == INF) continue;
        if(i + a[0] >= h){
            ans = min(ans, dp[i] + 1);
        }
    }
    if(ans == INF){
        cout << -1 << "\n";
    }else{
        cout << ans << "\n";
    }
}