今日はマーガレットを一杯飲みますか?[P5]

質問:https://www.acmicpc.net/problem/2728

ぶんかつ

動的プログラミング

✔解過程

dp[v+1][mony+1]サイズの配列を作成します.
dp[i][j]はi番棚を見たとき、j万元で買える組み合わせ数です.
d[0][0]=1であり、それぞれの高価な大麻を購入する組み合わせと購入しない組み合わせを追加する.

for (int i = 0; i < V; i++)
{
	for (int j = 0; j <= D; j++)
	{
		dp[i + 1][j] += dp[i][j]; //안 산 경우
		if (j + shop[i] <= D) //샀을 경우, 돈이 초과하는 경우는 제외
		{
			dp[i + 1][j + shop[i]] += dp[i][j];
		}
	}
}

このように,dp[v]の各位置には,0からmoneyの価格で購入した数が含まれる.
しかし、現在の状況では、どの状況が正しいのか分かりません.
同じ価格で買える場合でも、残りのお金と存在しない場合が混在します.
いったいどうやって区別すればいいのでしょうか.
ヒントは、総数を特定のマーガレット数を含むか、特定のマーガレット数を含まないかに分けることができることです.
例を挙げて説明します.
4つの販売台があり、それぞれ1、1、2、4万ウォンの携帯ケースだ.
上のdp式を使用して配列を埋め込む場合、図は次のようになります.

△インデックスは書いてありますが、値札はつけてありますので、ご注意ください.
最後のセルはすべての場合の数字で、マーガレットと非マーガレットを含む2つの文字に分けられます.
まず最初の0元格子はもちろん2は含まれていませんよね?
この場合、1、1、2、4が含まれていない場合、ここで2が含まれていれば2万ウォンになるはずです.

そして1万格も2を含まない場合-1万から2万元は含まれないから
ここに2万元を含む3万元の格子に該当する場合を加える

そして2万円の格子を見ましょうすでに2万元が含まれている場合は1種類ありますそれでは2-1=1種類の情況は2万元を含みません前の表に記入してください.

今は感じてるはず残りも埋めて

こつこつ~と全体の状況の数字がぴったり合っています
特定のマーガレットを含む場合は、含まない場合を除外と呼びます.
includeはexcludeから来たものと見なすことができ、考えればexcludeからincludeまでの場合はお金が残っている場合と見なすことができます.
すべての場合、これらの場合を除いて、答えを見つけることができます.
結論:
1.マーガレットを昇順に並べ替えた後、最初のマーガレットについて、合計数をincludeとexcludeに分離します(所有するお金より大きいお金はincludeに入れません).
2.includeに含まれる数を合計から減算します.
3.次のマーガレットについて、includeをincludeとexcludeに分離します.
4.繰り返し...
5.最初からマーガレットが買えない場合は、total=0で異常処理してください.そうでなければ、1はdp[0][0]になります.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

long long dp[31][1001];
vector<int> shop;
long long include[1001];
long long exclude[1001];

int main()
{
	long long T, V, D,tmp;
	long long total;
	scanf("%lld", &T);
	while (T--)
	{
		total = 0;
		for (int i = 0; i < 31; i++)
		{
			for (int j = 0; j < 1001; j++)
			{
				dp[i][j] = 0;
			}
		}
		for (int j = 0; j < 1001; j++)
		{
			include[j] = 0;
			exclude[j] = 0;
		}
		dp[0][0] = 1;
		scanf("%lld %lld", &V, &D);
		for (int i = 0; i < V; i++)
		{
			scanf("%lld", &tmp);
			shop.push_back(tmp);
		}
		sort(shop.begin(), shop.end());
		for (int i = 0; i < V; i++)
		{
			for (int j = 0; j <= D; j++)
			{
				dp[i + 1][j] += dp[i][j];
				if (j + shop[i] <= D)
				{
					dp[i + 1][j + shop[i]] += dp[i][j];
				}
			}
		}

		for (int k = 0; k <= D; k++)
		{
			total += dp[V][k];
			exclude[k] = dp[V][k];
		}
		
		for (int i = 0; i < V; i++)
		{
			for (int k = 0; k <= D; k++)
			{
				if (k + shop[i] <= D)
				{
					include[k + shop[i]] += exclude[k];
					exclude[k + shop[i]] -= exclude[k];
					total -= exclude[k];
				}
			}
			for (int k = 0; k <= D; k++)
			{
				exclude[k] = include[k];
				include[k] = 0;
			}
		}
		if (shop[0] > D)
		{
			total = 0;
		}
		printf("%lld\n", total);
		while (!shop.empty())
		{
			shop.pop_back();
		}
	}
}

各テストケースの時間的複雑さはO(VD+VlgV)であるべきである.