PKU 3093 Margaritas on the River Walk

http://acm.pku.edu.cn/JudgeOnline/problem?id=3093

• DP
• あかかじめ値段の昇順にソートしておく
• 安い店から順に辿っていき、買うか買わないかで分岐する
• 他の店で買えなくなるまで買うという条件を満たすため、自分が買わなかったマリゲータのうち最も安い物を覚えておく
• いずれも買えない場合は0を出力

//[どこまで見た][最初から連続して使ったのはどこまでか][金額]
static ll dp[32][32][1024];

int main()
{
	int N;
	cin >> N;
	for (int testCase = 1; testCase <= N; ++testCase) {
		int V, D;
		cin >> V >> D;
		vector<int> costs;
		for (int i = 0; i < V; ++i) {
			int cost;
			cin >> cost;
			costs.push_back(cost);
		}
		costs.push_back(10000);
		sort(costs.begin(), costs.end());

		if (costs.front() > D) {
			cout << testCase << " " << 0 << endl;
			continue;
		}

		memset(dp, 0, sizeof(dp));
		dp[0][0][0] = 1;
		for (int v = 0; v < V; ++v) {
			for (int i = 0; i < V; ++i) {
				for (int d = 0; d <= D; ++d) {
					if (!dp[v][i][d]) {
						continue;
					}

					// 買わないで次に行く
					dp[v + 1][i][d] += dp[v][i][d];

					// 買って次に行く
					if (d + costs[v] <= D) {
						if (v == i) {
							// ここまで全て購入した
							dp[v + 1][i + 1][d + costs[v]] += dp[v][i][d];
						} else {
							dp[v + 1][i][d + costs[v]] += dp[v][i][d];
						}
					}
				}
			}
		}

		ll answer = 0;
		for (int d = 0; d <= D; ++d) {
			for (int i = 0; i <= V; ++i) {
				if (dp[V][i][d] && D - d < costs[i]) {
					const ll value = dp[V][i][d];
					answer += value;
				}
			}
		}

		cout << testCase << " " << answer << endl;
	}
}