2019CSP-J T3 【纪念品】

|

Description

下载.png

Solutions

考虑使用 完全背包DP 来解题。

由于每天可以无限次交易，那么我们每一天都可以先把之前买进的全部卖出，再按最优方案购进。

我们可以通过下面这个例子来理解这种做法：

编号\天数 1 2 3 4
1号 10 20 30 10

1号第一天买入，第三天卖出明显是最优方案，利润为 $$20x（x表示个数）$$ ，我们以刚刚说的方法做。

假设第一天拥有 100 金币。

天数 买入个数 卖出个数 拥有的金币和物品的总价值
1 10 0 100
2 10 10 200
3 0 10 300

所以说明中途进行买卖是不会影响最优方案的。

但有些东西在中途需要进行买卖，那么我们就卖出后再算出当天最优方案，再购进当天的纪念品。

那怎么计算每天的最优方案呢？

要想赚得最多，最优方案肯定会满足以下条件：

1 购进的物品下一天会盈利。
2 购进的物品的利润（下一天价格比该天的高出的部分）相对较高但价格会相对较低
3 持有的金钱基本都会被花掉，用于买满足第一条条件的物品上，故最后剩下来的钱会比满足第一条条件的物品的当天价格都要小。

综上所述，最优方案可以用完全背包求。

所以，只需要先知道每一天持有的金币数，再做一遍完全背包求出当天可获得的最大价值，然后用这个最大价值求出下一天持有的金币数，就可求出最后一天持有的金币数，即答案。

这道题就做完了，详细细节见 代码 。

Code

1
#include<cmath>
2
#include<cstdio>
3
#include<cstring>
4
#include<iostream>
5
#include<algorithm>
6
using namespace std;
7
int n,m,p;
8
int a[101][101],b[101],h[10001],maxx,an;
9
bool bz[10001];
10
int main()
11
{
12
	freopen("souvenir.in","r",stdin);
13
	freopen("souvenir.out","w",stdout);
14
	scanf("%d%d%d",&m,&n,&p);
15
	for(int i=1;i<=m;i++)
16
	{
17
		for(int j=1;j<=n;j++)
18
		{
19
			scanf("%d",&a[i][j]);
20
		}
21
	}
22
	for(int i=1;i<=m;i++)
23
	{
24
		memset(h,0,sizeof(h));
25
		memset(bz,0,sizeof(bz));
26
		maxx=0;bz[0]=1;an=p;
27
		if(i==m)continue;
28
		for(int j=1;j<=n;j++)
29
		{
30
			if(a[i+1][j]-a[i][j]<=0)continue;
31
			for(int k=0;k<=min(p-a[i][j],maxx);k++)
32
			{
33
				if(bz[k]==1)
34
				{
35
					if(h[k+a[i][j]]<h[k]+(a[i+1][j]-a[i][j]))
36
					{
37
						h[k+a[i][j]]=h[k]+(a[i+1][j]-a[i][j]);
38
						bz[k+a[i][j]]=1;
39
						maxx=max(maxx,k+a[i][j]);
40
					}
41
				}
42
			}
43
		}
44
		for(int j=1;j<=maxx;j++)
45
		{
46
			an=max(an,p+h[j]);
47
		}
48
		p=an;
49
	}
50
	printf("%d",p);
51
	return 0;
52
}