算法用的是某牛的方法：将两个值（时间和MM数）转化为一个值（每泡一个MM加200000分-时间），求出最大得分再转化成时间输出。但是为什么只对70，半对不对的？谢谢

测试结果1: 通过本测试点|有效耗时62ms

测试结果2: 通过本测试点|有效耗时47ms

测试结果3: 通过本测试点|有效耗时47ms

测试结果4: 测试结果错误.错误结果为:9241 正确结果应为:5923

测试结果5: 通过本测试点|有效耗时47ms

测试结果6: 测试结果错误.错误结果为:142 正确结果应为:134

测试结果7: 通过本测试点|有效耗时47ms

测试结果8: 通过本测试点|有效耗时46ms

测试结果9: 测试结果错误.错误结果为:2675 正确结果应为:3345

测试结果10: 通过本测试点|有效耗时47ms

#include "stdio.h"

int RMB,RP,N;

int f[100][100];

int rmb[101];

int rp[101];

int w[101];

int main()

{

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

int i,j,k;

scanf("%d",&N);

for(i=1;i<=N;i++)

{

scanf("%d %d %d",&rmb[i],&rp[i],&w[i]);

w[i]=200000-w[i];

}

scanf("%d %d",&RMB,&RP);

for(k=1;k<=N;k++)

for(i=RMB;i>=rmb[k];i--)

for(j=RP;j>=rp[k];j--)

{

if(f[i-rmb[k]][j-rp[k]]+w[k]>f[i][j])

f[i][j]=f[i-rmb[k]][j-rp[k]]+w[k];

}

printf("%d",200000-(f[RMB][RP]%200000));

return 0;

}

你在 if(f[i-rmb[k]][j-rp[k]]+w[k]>f[i][j])少考虑了一种情况

具体应如下：

if(dp[i][j]<dp[i-rmb[i]][j-rp[i]]+1||(dp[i][j]==dp[i-rmb[i]][j-rp[i]]+1&&t[i][j]>t[i-rmb[i]][j-rp[i]]+tim[i]))

dp[i][j]=dp[i-rmb[i]][j-rp[i]]+1,t[i][j]=t[i-rmb[i]][j-rp[i]]+tim[i];

t[i][j]为最少时间

回复 沙发892611452 的帖子

你的这种方法我理解，在“可以有更大MM数”和“保证MM数最大情况下可以用更少时间”时分别更新dp[][]和t[][]，但我用的是另一种方法：给MM数一个极大的权(200000)，和用时看成同一个价值：w[i]=200000*1-time[i]，从而转化成01背包。我不知道这个方法哪里错了..

回复 沙发892611452 的帖子

我用这种方法也只能对60分。。

测试结果1: 通过本测试点|有效耗时62ms

测试结果2: 测试结果错误.错误结果为:3170 正确结果应为:3160

测试结果3: 通过本测试点|有效耗时47ms

测试结果4: 测试结果错误.错误结果为:3477 正确结果应为:5923

测试结果5: 通过本测试点|有效耗时47ms

测试结果6: 测试结果错误.错误结果为:62 正确结果应为:134

测试结果7: 通过本测试点|有效耗时47ms

测试结果8: 通过本测试点|有效耗时47ms

测试结果9: 测试结果错误.错误结果为:886 正确结果应为:3345

测试结果10: 通过本测试点|有效耗时47ms

#include "stdio.h"

int f[100][100];//最大MM数

int t[100][100];//保证MM数最大时的最少时间

int rmb[101];

int rp[101];

int time[101];

int N,RP,RMB;

int main()

{

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

memset(t,0,sizeof(t));

int i,j,k;

scanf("%d",&N);

for(i=1;i<=N;i++)

scanf("%d %d %d",&rmb[i],&rp[i],&time[i]);

scanf("%d %d",&RMB,&RP);

for(i=1;i<=N;i++)

for(j=RMB;j>=rmb[i];j--)

for(k=RP;k>=rp[i];k--)

{

if(f[j-rmb[i]][k-rp[i]]+1>f[j][k] || (f[j-rmb[i]][k-rp[i]]+1==f[j][k] && t[j-rmb[i]][k-rp[i]]+time[i]<t[j][k]))

{

f[j][k]=f[j-rmb[i]][k-rp[i]]+1;

t[j][k]=t[j-rmb[i]][k-rp[i]]+time[i];

}

}

printf("%d",t[RMB][RP]);

return 0;

}

。。。。。。。。。。。。。。。。。。。。。。。。