SRM 232 DIV1 Hard SalesPromotion

問題 Editorial

問題

商品がいくつかある。
商品にはそれぞれ"pointValue"と値段がある。
ポイントをその商品のpointValueだけ使ってその商品を無料で買うことができる。
また、半額ポイントというものもあって、それを1つ使って1つの商品を半額で買える。
ポイントを使わなくても値段からdiscountパーセントの値引きで買うことができる。
半額と値引きの値段は全て切り上げて計算される。
ポイント・半額ポイント・値引きは重複させることができない。
今ポイントをpoints、半額ポイントをhalfPrice持っていて、itemsを全て買いたい。
また、ポイントと半額ポイントは全て使いきりたい。
このとき、支払いを最小化せよ

• 1 <= |items| <= 50
• 1 <= 商品の値段 <= 99999
• 1 <= 商品のpointValue <= 9999
• 0 <= points <= 15000
• 0 <= halfPrice <= |items|
• 0 <= discount <= 49
• ポイントと半額ポイントを使い切る方法が1つ以上存在する

解答

単純なDP。
(何番目の商品まで見て * 残りポイント * 残り半額ポイント)
メモリを節約するために2つだけ覚える。1つだけ覚えてもできる

コメント

"round up"を見逃していてFailed。
整数の割り算・パーセンテージでは丸め方向がどちらなのか、絶対に原文をきちんと読んで確認しよう

コード

#include <string>
#include <vector>
#include <sstream>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define INF 0x3f3f3f3f
using namespace std;
int pointValue[55], priceHalf[55], priceDiscount[55];
int dp[2][15001][51];
struct SalesPromotion {
	int n;
	int bestPrice(int points, int halfPrice, int discount, vector <string> items) {
		n = items.size();
		rep(i, n) {
			stringstream ss(items[i]);
			int v, p;
			ss >> v >> p;
			pointValue[i] = v;
			priceHalf[i] = (p + 1) / 2;
			priceDiscount[i] = (p * (100 - discount) + 99) / 100;
		}
		for(int i = n; i >= 0; i --) rer(p, 0, points) rer(h, 0, halfPrice) {
			int r = INF;
			if(i == n) {
				if(p == 0 && h == 0) r = 0;
			}else {
				if(p >= pointValue[i]) r = min(r, dp[(i+1)&1][p-pointValue[i]][h]);
				if(h) r = min(r, priceHalf[i] + dp[(i+1)&1][p][h-1]);
				r = min(r, priceDiscount[i] + dp[(i+1)&1][p][h]);
			}
			dp[i&1][p][h] = r;
		}
		return dp[0][points][halfPrice];
	}
};