[vijos1428]贪婪格尔曼

发布于 2017-09-12  27 次阅读



题目(vijos)
这题就是个背包......只不过是二维费用的背包而已。
设dp[j][k]表示希望小狗叫j次,大狗叫k次时的最小费用。
我们又知道,每种饼干只能买一次,
所以这就是个0-1背包问题。
另外,这题适合倒推,因为可能会出现叫声大于所需叫声的情况,这时只需要用dp[0][0]表示就行。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
const ll INF=999999999999999;
int n,S,B;
ll s[1005],b[1005],c[1005];
ll dp[55][55];
int main()
{
	scanf(
	for (int i=0;i<=S;++i)
		for (int j=0;j<=B;++j)
			dp[i][j]=INF;
	dp[0][0]=0;
	for (int i=1;i<=n;++i)
	{
		scanf(
		c[i]*=2;
	}
	for (int i=1;i<=n;++i)
	{
		for (int j=S;j>=0;--j)
		{
			for (int k=B;k>=0;--k)
			{
				if (j-s[i]<=0 && k-b[i]<=0)
					dp[j][k]=min(dp[j][k],dp[0][0]+c[i]);
				if (j-s[i]<=0 && k-b[i]>0)
					dp[j][k]=min(dp[j][k],dp[0][k-b[i]]+c[i]);
				if (j-s[i]>0 && k-b[i]<=0)
					dp[j][k]=min(dp[j][k],dp[j-s[i]][0]+c[i]);
				if (j-s[i]>0 && k-b[i]>0)
					dp[j][k]=min(dp[j][k],dp[j-s[i]][k-b[i]]+c[i]);
			}
		}
	}
	printf(
	return 0;
}