AOJ 0106 Discounts of Buckwheat

404 Not Found

昨日はじめてナップザック問題解いたので今度はこれをDP。解けた嬉しい。

ちょっと悪問てか、勝手に解釈して勝手に最も適切に解いたつもりだったんだけどWAでイラっとした。

例えばそば粉1100g買う場合に、そのまま1100gだけ買おうとすると

B店 300g*2袋(1100円) + C店 500g*1袋(550円)で1950円かかる。

んだけども そば粉1200g買う場合には、

B店 300*4袋(割引後価格1870円) = 1870円 で買える。

こっちの方が量多いわ安いわで、お買い得。

でそれを考慮したのがコメントアウト部分だったんですが、それをするとWAだったので泣きました。

#include <iostream>
#include <vector>
using namespace std;
#define MAXVALUE (1<<21)
vector<int> dp(5000+1,MAXVALUE);

void init(){
	int item[6] = {200,300,500,1000,1200,1500};
	int price[6]= {380,550,850,1520,1870,2244};
	
	dp[0]=0;

	for(int k=0;k<6;k++){
		for(int i=0;i+item[k]<=5000;i++){
			dp[i+item[k]] = min( dp[i+item[k]] , dp[i]+price[k] );
		}
	}
}

int main(){
	init();
	int n,mi;
	while(cin >> n && n){
		mi = dp[n];
		/*for(int i=n;i<=5000;i++){
			mi = min(dp[i],mi);
		}*/
		cout << mi << endl;
	}
}