P3983 赛斯石(双背包)

这题不算难的，但是脑子真的特别乱.....传送门

\(Ⅰ.物品可以拆开来但船不能拆开来，所以1-10载重船的最大收益完全可以用背包求出来。\)

\(Ⅱ.最后一定是选一些船走，而船的收益已经固定。所以用完全背包求出质量为n时的最大收益。\)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n;

ll b[12]={0,1,3,5,7,9,10,11,14,15,17};

ll a[12],f[12],dp[100009];

int main()

{

	cin>>n;

	for(int i=1;i<=10;i++)	cin>>a[i];

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

	{

		for(int j=i;j<=10;j++)

			f[j]=max(f[j],f[j-i]+a[i]);//总重量为j时最大收益

	}

	for(int i=1;i<=10;i++)	f[i]-=b[i];

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

	{

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

			dp[j]=max(dp[j],dp[j-i]+f[i]);

	}

	cout<<dp[n];

}

巴特西

P3983 赛斯石(双背包)

最新文章

热门文章