绝望，7个点超时，3个点对

AR219 @ 2017-05-25 20:06:33

var
  money,n,i,j,value:longint;
  price,importance,belong:array[1..60] of longint;
  f1,f:array[0..32000] of longint;
function max(a,b:longint):longint;
begin
  if a>b then exit(a) else exit(b);
end;
begin
  readln(money,n);
  for i:=1 to n do
    readln(price[i],importance[i],belong[i]);
  for i:=1 to n do
    if belong[i]=0 then
    begin
      fillchar(f1,sizeof(f1),0);
      for j:=1 to n do
        if belong[j]=i then
          for value:=money downto price[j] do
            f1[value]:=max(f1[value-price[j]]+importance[j]*price[j],f1[value]);
      for value:=money downto price[i] do
        for j:=value-price[i] downto 0 do
          f[value]:=max(f[value-j-price[i]]+f1[j]+importance[i]*price[i],f[value]);
    end;
    writeln(f[money]);
end.

by lzoi_lhy @ 2017-06-08 14:39:38

我也是

#include<cstdio>
int n,v,fa,w[61],c[61],son[61],bro[61],dp[61][32001];
int dfs(int u,int val)
{
    if (dp[u][val]) return dp[u][val];
    if (bro[u])
    {
        dfs(bro[u],val);
        dp[u][val]=dp[bro[u]][val];
    }
    if (w[u]>val) return dp[u][val];
    for (int k=0;k<=val-w[u];++k)
    {
        int num=c[u];
        if (son[u]) num+=dfs(son[u],k);
        if (bro[u]) num+=dfs(bro[u],val-w[u]-k);
        dp[u][val]=dp[u][val]>num?dp[u][val]:num;
    }
    return dp[u][val];
}
int main()
{
    scanf("%d%d",&v,&n);
    for (int i=1;i<=n;++i)
    {
        scanf("%d%d%d",&w[i],&c[i],&fa);
        if (son[fa]) bro[i]=son[fa];
        son[fa]=i;c[i]*=w[i];
    }
    printf("%d\n",dfs(0,v));
}

by 飞翔的金鱼 @ 2018-02-08 17:55:13

我是A三个点，WA七个点