以下为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。。。