建议大规模修改数据
查看原帖
建议大规模修改数据
1636470
shandianhailan楼主2025/6/15 16:23

提供本人做题的代码。

以下为100pts的代码。

//100pts
#include<iostream>
using namespace std;
const int N=1e5;
using ll=long long;
struct node { ll v,p,cnt; }a[N];//体力为V,一棵树每次能摘的桃数为P,每棵树可以摘的次数为CNT 
ll dp[N],idx,W;
void _0_1bag(ll P,ll V)
{
	for(int j=W;j>=V;j--) 
		dp[j]=max(dp[j],dp[j-V]+P);
}
void CompleteBag(ll P,ll V)
{
	for(int j=V;j<=W;j++)
		dp[j]=max(dp[j],dp[j-V]+P);
}
void bin_fill(int i,node a[])
{
	if(W<=a[i].v*a[i].cnt) //这个地方对照下面的代码
	{
		CompleteBag(a[i].p,a[i].v);
		return;
	}
	for(int k=1;k<=a[i].cnt;k<<=1)
	{
		_0_1bag(a[i].p*k,a[i].v*k);
		a[i].cnt-=k;
	}	
	if(a[i].cnt>0) _0_1bag(a[i].p*a[i].cnt,a[i].v*a[i].cnt);
	return;
}
int main()
{
	int n,m,T,A;
	cin>>n>>m>>T>>A;
	W=min(T,A-1);
	for(int i=1;i<=n;i++) 
		for(int j=1;j<=m;j++) cin>>a[++idx].p;
	idx=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) cin>>a[++idx].cnt;
	idx=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) a[++idx].v=i+j<<1;
	for(int i=1;i<=idx;i++) bin_fill(i,a);	
	cout<<dp[W]<<endl;
	return 0;
}

这是AC的链接

//90pts
#include<iostream>
using namespace std;
const int N=1e5;
using ll=long long;
struct node { ll v,p,cnt; }a[N];//体力为V,一棵树每次能摘的桃数为P,每棵树可以摘的次数为CNT 
ll dp[N],idx,W;
void _0_1bag(ll P,ll V)
{
	for(int j=W;j>=V;j--) 
		dp[j]=max(dp[j],dp[j-V]+P);
}
void CompleteBag(ll P,ll V)
{
	for(int j=V;j<=W;j++)
		dp[j]=max(dp[j],dp[j-V]+P);
}
void bin_fill(int i,node a[])
{
	if(W<=a[i].p*a[i].cnt)//这个地方有问题,具体对照100pts的代码 
	{
		CompleteBag(a[i].p,a[i].v);
		return;
	}
	for(int k=1;k<=a[i].cnt;k<<=1)
	{
		_0_1bag(a[i].p*k,a[i].v*k);
		a[i].cnt-=k;
	}	
	if(a[i].cnt>0) _0_1bag(a[i].p*a[i].cnt,a[i].v*a[i].cnt);
	return;
}
int main()
{
	int n,m,T,A;
	cin>>n>>m>>T>>A;
	W=min(T,A-1);
	for(int i=1;i<=n;i++) 
		for(int j=1;j<=m;j++) cin>>a[++idx].p;
	idx=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) cin>>a[++idx].cnt;
	idx=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) a[++idx].v=i+j<<1;
	for(int i=1;i<=idx;i++) bin_fill(i,a);	
	cout<<dp[W]<<endl;
	return 0;
}

上面这时90pts的代码,有一处错误在代码中已经标出来了。数据水的有点过了,,这种 逻辑性的细节 错误居然也能过90pts。。。

2025/6/15 16:23
加载中...