讨论 / WA50,求解释一下错了哪里
all blue 2014-03-05 20:57:58
点我顶贴 收藏 删除
#include<stdio.h>

int n;

int m,r;

struct mm

{

int rmb,rp,time;

};

mm M[101];

struct f

{

int data,time;

};

f d[101][101][1001];

int max(int as,int ad)

{

if (as>ad) return as;

else return ad;

}

int dp(int i,int j,int k)

{

int &ans=d[i][j][k].data;

if (ans>0) return ans;

if (j>=M[i].rmb&&k>=M[i].rp)

{

if (dp(i-1,j-M[i].rmb,k-M[i].rp)+1>dp(i-1,j,k))

{

d[i][j][k].data=d[i-1][j-M[i].rmb][k-M[i].rp].data+1;

d[i][j][k].time=d[i-1][j-M[i].rmb][k-M[i].rp].time+M[i].time;

}

else

{

d[i][j][k].data=d[i-1][j][k].data;

d[i][j][k].time=d[i-1][j][k].time;

}

}

else

{

d[i][j][k].data=dp(i-1,j,k);

d[i][j][k].time=d[i-1][j][k].time;

}

return d[i][j][k].data;

}

int main()

{

scanf("%d",&n);

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

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

scanf("%d%d",&m,&r);

for (int i=0;i<=m;i++)

for (int j=0;j<=r;j++)

d[0][i][j].data=1;

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

for (int j=0;j<=m;j++)

for (int k=0;k<=r;k++)

d[i][j][k].time=0;

int max=dp(n,m,r);

int mmm=1<<30;

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

for (int j=0;j<=m;j++)

for (int k=0;k<=r;k++)

if (d[i][j][k].data==max)

if (mmm>d[i][j][k].time) mmm=d[i][j][k].time;

printf("%d\n",mmm);

return 0;

}

#1 tjsudys@2014-03-31 22:21:42
回复 删除
#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

int girl[101][3]={0};

int n;

int m,r;

int f[102][102][102][2]={0};

int max(int a,int b,int c)

{

if(a<b)a=b;

if(a<c)a=c;

return a;

}

int max(int a,int b,int c,int d)

{

if(a<b)a=b;

if(a<c)a=c;

if(a<d)a=d;

return a;

}

int min(int a,int b,int c,int d)

{

if(a>b)a=b;

if(a>c)a=c;

if(a>d)a=d;

return a;

}

int main()

{

cin>>n;

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

{

cin>>girl[i][0]>>girl[i][1]>>girl[i][2];

}

cin>>m>>r;

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

for(int i=m;i>=0;i--)

for(int j=r;j>=0;j--)

{

if(i<girl[t][0]||j<girl[t][1])

{ f[i][j][t][0]=f[i][j][t-1][0];

f[i][j][t][1]=f[i][j][t-1][1];

}

else

if(f[i][j][t-1][0]>f[i-girl[t][0]][j-girl[t][1]][t-1][0]+1)

{

f[i][j][t][0]=f[i][j][t-1][0];

f[i][j][t][1]=f[i][j][t-1][1];

}

else

if(f[i][j][t-1][0]<f[i-girl[t][0]][j-girl[t][1]][t-1][0]+1)

{

f[i][j][t][0]=f[i-girl[t][0]][j-girl[t][1]][t-1][0]+1;

f[i][j][t][1]=f[i-girl[t][0]][j-girl[t][1]][t-1][1]+girl[t][2];

}

else

if(f[i][j][t-1][1]<f[i-girl[t][0]][j-girl[t][1]][t-1][1]+girl[t][2])

{

f[i][j][t][0]=f[i][j][t-1][0];

f[i][j][t][1]=f[i][j][t-1][1];

}

else

{

f[i][j][t][0]=f[i-girl[t][0]][j-girl[t][1]][t-1][0]+1;

f[i][j][t][1]=f[i-girl[t][0]][j-girl[t][1]][t-1][1]+girl[t][2];

}

}

int maxgirl=0,mint;

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

for(int i=m;i>=0;i--)

for(int j=r;j>=0;j--)

{

if(f[i][j][t][0]>maxgirl)

{

mint=f[i][j][t][1];

maxgirl=f[i][j][t][0];

}

if(f[i][j][t][0]==maxgirl&&mint>f[i][j][t][1])

{

mint=f[i][j][t][1];

}

}

cout<<mint;

return 0;

}

#2 tjsudys@2014-03-31 22:26:38
回复 删除
你可以比较下自己错误时输出的数据与正确答案大小比较

我有次提交错误是因为判断结束后 赋值时写错了 你可能也是出了这个问题

找到了

如果泡到的妹子数量相同情况下 选择时间较少的方案 ,这个没有在你的代码中表现出来

查看更多回复
提交回复