281. 硬币

題目連結：硬币

*算法分析：

初看起來就是個簡單的多重背包， C i C_i Ci​不大于1000，二進制拆分最多拆出10個數，這樣時間複雜度在 1 0 8 10^8 108，勉強。送出後，資料強，逾時。以下是标準二進制拆分逾時代碼。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n, m, A[110], a[1010], f[100010];
int main()  // 二進制拆分，逾時  
{
	while (1)
	{
		scanf("%d%d", &n, &m);
		if (!n && !m) break;
		for (int i = 1; i <= n; ++i) scanf("%d", &A[i]);
		int s = 0;
		for (int i = 1; i <= n; ++i)
		{
			int c; scanf("%d", &c);
			int t = 1;
			while (c >= t)
			{
				a[++s] = t * A[i];
				c -= t; 
				t *= 2;
			}
			if (c > 0) a[++s] = c * A[i];
		}
		memset(f, 0, sizeof(f));
		f[0] = 1;
		for (int i = 1; i <= s; ++i)
			for (int j = m; j >= a[i]; --j)
					f[j] = f[j] || f[j-a[i]];
				
		int ans = 0;
		for (int j = 1; j <= m; ++j) ans += f[j];
		printf("%d\n", ans);
	}
	return 0;
}
           

據說用單調隊列優化多重背包，可以達到 O ( n ∗ m ) O(n*m) O(n∗m)。以後有時間再補充。下面算法參考進階指南。想法很巧妙。

用 u s e d [ j ] used[j] used[j]表示在 f [ j ] f[j] f[j]階段為i時，體積為j，此時為true的情況下至少需要多少枚第i種硬币。采用一種貪心政策：讓 u s e d [ j ] used[j] used[j]轉移時，盡量不選第i種硬币。

也就是，當 f [ j − a [ i ] ] f[j-a[i]] f[j−a[i]]為true時，如果此時 f [ j ] f[j] f[j]已經為true，則不執行dp轉移。否則才讓 f [ j ] = f [ j ] − a [ i ] f[j]=f[j]-a[i] f[j]=f[j]−a[i]，并且 u s e d [ j ] = u s e d [ j − a [ i ] ] + 1 used[j]=used[j-a[i]] + 1 used[j]=used[j−a[i]]+1。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n, m, A[110], C[110], f[100010], used[100010];
int main()  
{
	while (1)
	{
		scanf("%d%d", &n, &m);
		if (!n && !m) break;
		for (int i = 1; i <= n; ++i) scanf("%d", &A[i]);
		for (int i = 1; i <= n; ++i) scanf("%d", &C[i]);
		
		memset(f, 0, sizeof(f));
		f[0] = 1;
		for (int i = 1; i <= n; ++i)
		{
			for (int j = 0; j <= m; ++j) used[j] = 0;
			for (int j = A[i]; j <= m; ++j)
				if (!f[j] && f[j-A[i]] && used[j-A[i]] < C[i])
				{
					f[j] = 1;
					used[j] = used[j-A[i]] + 1;
				}
		}
				
		int ans = 0;
		for (int j = 1; j <= m; ++j) ans += f[j];
		printf("%d\n", ans);
	}
	return 0;
}