讨论 / 递归怎么做到不超时呢???
yujunzhe 2015-05-20 07:29:57
点我顶贴 收藏 删除
var a,b,i,m:longint;

wp:array[1..60,1..2] of longint;

xz:array[1..60] of boolean;

fj:array[1..60] of longint;

procedure px;

var i,s:longint;

begin

s:=0;

for i:=1 to b do

if xz[i]

then s:=s+wp[i,1]*wp[i,2];

if s>m

then m:=s;

end;

procedure qj(d,s:longint);

var i:longint;

begin

for i:=1 to 2 do

begin

if (wp[d,1]>s) and (i=1)

then continue;

if (i=1) and (fj[d]>0) and (not xz[fj[d]])

then continue;

if i=1

then xz[d]:=true

else xz[d]:=false;

px;

if d<b

then begin

if i=1

then qj(d+1,s-wp[d,1])

else qj(d+1,s);

end;

end;

end;

begin

readln(a,b);

for i:=1 to b do

readln(wp[i,1],wp[i,2],fj[i]);

qj(1,a);

writeln(m);

end.

#1 sunjunhan@2015-08-21 20:08:48
回复 删除
打标
#2 Y阿杜@2015-09-25 22:00:32
回复 删除
#include <iostream>

#include <cmath>

#include <memory.h>

using namespace std;

int dp[30001]={0};

int main()

{

int money,n;

cin>>money>>n;

int i=1,j;

int zhu[60][2],link1[60][2]={0},link2[60][2]={0};

for(j=0;j<n;++j)

{

int v,p,q;

cin >> v >> p >> q;

if(q == 0){zhu[i][0] = v;zhu[i][1] = v*p;++i;}

else if(link1[q][0] == 0){link1[q][0] = v;link1[q][1] = v*p;}

else{link2[q][0] = v;link2[q][1] = v*p;}

}

memset(link1,0,sizeof(link1));

memset(link2,0,sizeof(link2));

int maxx = 0;

int k;

for(j=1;j<i;++j){

for(k=money;k>=zhu[j][0];k--)

{

dp[k]=max( dp[k] , dp[k-zhu[j][0]]+zhu[j][1] );

if(k-zhu[j][0]-link1[j][0]>=0)

dp[k]=max(dp[k],dp[k-zhu[j][0]-link1[j][0]]+zhu[j][1]+link1[j][1]);

if(k-zhu[j][0]-link2[j][0]>=0)

dp[k]=max(dp[k],dp[k-zhu[j][0]-link2[j][0]]+zhu[j][1]+link2[j][1]);

if(k-zhu[j][0]-link1[j][0]-link2[j][0]>=0)

dp[k]=max(dp[k],dp[k-zhu[j][0]-link1[j][0]-link2[j][0]]+zhu[j][1]+link1[j][1]+link2[j][1]);

maxx=max(maxx,dp[k]);

}

}

cout << maxx;

return 0;

}

#3 Y阿杜@2015-09-25 22:00:58
回复 删除
回复 #1 sunjunhan:#include <iostream>

#include <cmath>

using namespace std;

int dp[30001]={0};

int main()

{

int money,n;

cin>>money>>n;

int i=1,j;

int zhu[60][2]={0},link1[60][2]={0},link2[60][2]={0};

for(j=0;j<n;++j)

{

int v,p,q;

cin >> v >> p >> q;

if(q == 0){zhu[i][0] = v;zhu[i][1] = v*p;}

else if(link1[q][0] == 0){link1[q][0] = v;link1[q][1] = v*p;}

else{link2[q][0] = v;link2[q][1] = v*p;}

++i;

}

int maxx = 0;

int k;

for(j=1;j<i;++j){

for(k=money;k>=zhu[j][0];k--)

{

dp[k]=max( dp[k] , dp[k-zhu[j][0]]+zhu[j][1] );

if(k-zhu[j][0]-link1[j][0]>=0)

dp[k]=max(dp[k],dp[k-zhu[j][0]-link1[j][0]]+zhu[j][1]+link1[j][1]);

if(k-zhu[j][0]-link2[j][0]>=0)

dp[k]=max(dp[k],dp[k-zhu[j][0]-link2[j][0]]+zhu[j][1]+link2[j][1]);

if(k-zhu[j][0]-link1[j][0]-link2[j][0]>=0)

dp[k]=max(dp[k],dp[k-zhu[j][0]-link1[j][0]-link2[j][0]]+zhu[j][1]+link1[j][1]+link2[j][1]);

maxx=max(maxx,dp[k]);

}

}

cout << maxx;

return 0;

}

#4 Tiancrispdoinb@2020-02-10 11:13:58
回复 删除
记忆化搜索不就好了,和状态转移一样的时间
查看更多回复
提交回复