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.

打标

#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;

}

回复 #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;

}

记忆化搜索不就好了，和状态转移一样的时间

记忆化搜索是一个较为明智的选择

关于递归超时的解决办法还有:

转成递推

转成迭代

转成搜索+剪枝

打表

......

希望lz能满意