AOJ 0288 - Knocker of the Gigas Cedar

RE．Ω＼ζ°)ﾁｰﾝ．

解法

経験値は100より多くあっても意味がないことに注意する．
dp[i][j] := 樹の残りの耐久力がi，自分の経験値がjのときから何回で樹を倒せるか．
これはO(DN)(定数に100がつく)で更新できる．

コード

#include <cstdio>
#include <cstring>
#include <algorithm>

int D, N;
int dp[101][101];
int A[100], E[100], R[100];

int main(){
    while(scanf("%d %d", &D, &N), D || N){
        for(int i=0;i<N;i++){
            scanf("%d %d %d", A+i, E+i, R+i);
        }

        for(int i=0;i<=D;i++){
            for(int j=0;j<=100;j++){
                dp[i][j] = 1001001001;
            }
        }

        dp[D][0] = 0;
        for(int i=D;i>=0;i--){
            for(int j=0;j<=100;j++){
                for(int k=0;k<N;k++){
                    if(j >= R[k]){
                        int ni = std::max(i-A[k],0),
                            nj = std::min(j+E[k],100);
                        dp[ni][nj] = std::min(dp[ni][nj], dp[i][j] + 1);
                    }
                }
            }
        }

        int res = 1001001001;
        for(int i=0;i<=100;i++){
            res = std::min(res, dp[0][i]);
        }

        if(res != 1001001001){printf("%d\n", res);}
        else{puts("NA");}
    }