はやし屋

競技プログラミングのメモ きたない

0106: Discounts of Buckwheat

悪問と聞いたがなんとなくやったら出来た
最近dpの理解が深まります

int w[] = {200 , 300 , 500 , 1000 , 1200 , 1500};
int p[] = {380 , 550 , 850, 380*5*0.8 , 550*4*0.85 , 850*3*0.88};
vector < int > dp(5555,INF);// weight
  
void init(){
  dp[0] = 0;
  for(int i = 0 ; i < 6 ; ++i){
    for(int j = 0 ;j+w[i] <= 5555; ++j){
      dp[j+w[i]] = min(dp[j+w[i]],dp[j]+p[i]);
    }
  }
}
  
int main(){
  init();
  int n;
  while(cin >> n && n)cout << dp[n] << endl;
}