树形dp迷之TLE,求大神指点T-T

P1064 [NOIP2006 提高组] 金明的预算方案

controlf1 @ 2017-07-19 10:59:37

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int n,m;
int dp[61][61][3201];f[i][j][k]  从I的前J个孩子中选,共花费K*10元的最大价值
struct node{
    int v;int fa;int p;
    int num;
    int sumson;
    int son[10];
};
node a[100];
inline int ra()
{
     int x=0;char ch=getchar();int flag=1;
     while(ch>'9'||ch<'0'){if(ch=='-')ch=getchar();}
     while(ch>='0'&&ch<='9'){x*=10;x+=ch-'0';ch=getchar();}
     return x*flag;
}
void dpdp(int now);
int main()
{
    n=ra();n/=10;
    m=ra();
    for(int i=1;i<=m;i++)
    {
        a[i].p=ra();
        a[i].v=ra()*a[i].p;
        a[i].p/=10;
        int fa=ra();
        a[fa].sumson++;
        a[fa].son[a[fa].sumson]=i;
    }
    dpdp(0);
    int maxn=0;
    for(int i=1;i<=n;i++)maxn=max(maxn,dp[0][a[0].sumson][i]);
    cout<<maxn;
    return 0;
}
void dpdp(int now)
{
    if(a[now].sumson==0)
    {
        return;
    }
    else
    {
    for(int i=1;i<=a[now].sumson;i++)dpdp(a[now].son[i]);
    for(int i=1;i<=a[now].sumson;i++)
      for(int j=1;j<=n;j++)
        if(j>=a[a[now].son[i]].p)dp[now][i][j]=max(dp[now][i][j],dp[now][i-1][j-a[a[now].son[i]].p]+a[a[now].son[i]].v);
        else dp[now][i][j]=dp[now][i-1][j];
    }
}

n也/10了,自己下第一组数据跑得很快,为什么洛谷上全超时了??T-T

求大神指点;


by 飞翔的金鱼 @ 2018-02-08 17:54:21

大神啊,居然用树形dp


|