CSP-J2019 纪念品

Description：

Solution：

第一天买入，第二天卖出，在干些别的，再把第二天刚卖出的再买回来，就相当于是啥也没干。也就是说手中的物品本身要算在手中的钱中。这也就是为什么 dp 的状态可以直接从前一天继承过来。然后就是跑 n 遍完全背包。

Code：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

typedef long long ll;

const int N = 101, MAX=1e4+1;

ll t,n,m;

ll p[N][N],f[MAX];

int main()

{

	scanf("%lld%lld%lld",&t,&n,&m);

	for(int i=1;i<=t;++i)

		for(int j=1;j<=n;++j)

			scanf("%lld",&p[i][j]);

	for(int i=2;i<=t;++i)

	{

		memset(f,0,sizeof(f));

		for(int j=1;j<=n;++j)

		{

			for(int k=p[i-1][j];k<=m;++k)

			{

				f[k]=max(f[k],f[k-p[i-1][j]]+p[i][j]-p[i-1][j]);

			}

		}

		m+=f[m];

	}

	printf("%lld\n",m);

	return 0;

}

吐槽一下，为啥pj的T3有变得比T4难的趋势啊。。。

巴特西

CSP-J2019 纪念品

Description：

Solution：

Code：

最新文章

热门文章