ふぁー

これは…

MonsterValley

結局他人の写経してた。
ひとつ身に付けると使わなくてもいいところで使ってしまうクセ何とかならないかなぁ…
dreadをkeyにしたDPって(；・∀・)
逆ですよね、わかりますorz

class MonstersValley {
public:
   int minimumPrice( vector<long long> dread, vector <int> price ) {
       ll dp[100][200];
       int pos[100][200];
       memset(dp, 0, sizeof(dp));
       memset(pos, 0, sizeof(pos));
       pos[0][0]=1;
       int n=dread.size();
       
       for (int i=0; i<n; i++) {
           for (int j=0; j<110; j++) {
               if (pos[i][j]) {
                   dp[i+1][j+price[i]] = max(dp[i+1][j+price[i]], dp[i][j]+dread[i]);
                   pos[i+1][j+price[i]] = 1;
                   if (dread[i]<=dp[i][j]) {
                       dp[i+1][j]=max(dp[i+1][j], dp[i][j]);
                       pos[i+1][j] = 1;
                   }
               }
           }
       }
       
       for (int i=0; i<110; i++) if (pos[n][i]==1) return i;
   }
};