HDU 4169 UVALive 5741 Wealthy Family

나무 모양의 배낭.DP가 밀고 당기는 아이디어가 쉬워요...
그러나 노드가 15만 개가 있기 때문에 공간의 복잡도를 막론하고 dp수 그룹 dp[150000+10][300+10]를 켜면 초기화가memset(dp,-1,sizeof dp)이면 반드시 시간을 초과한다.
그래서 상태수 가지치기가 필요해...즉 이 노드의 최대 조합 수량을 기록한다.
UVALive는 메모리를 제한하지 않기 때문에 dp[150000+10][300+10]는 AC를 할 수 있고 HDU 4169는 메모리 크기를 제한하기 때문에 공간의 복잡도를 최적화해야 한다.
메모리 최적화 후의 코드는 HDU에서 C++가 AC를 할 수 있고 G++는 여전히 MLE이다.

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

const int maxn=150000+10;
struct Node
{
    int val;
    int fa;
    queue<int *>Q;
    vector<int>f;
}node[maxn];
int n,k,root;
int cnt[maxn];
int ans;

void init()
{
    memset(cnt,0,sizeof cnt);
    for(int i=1;i<=n;i++)
    {
        while(!node[i].Q.empty()) node[i].Q.pop();
        node[i].f.clear();
    }
}

void read()
{
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&node[i].fa,&node[i].val);
        if(!node[i].fa) root=i;
        else node[node[i].fa].f.push_back(i);
    }
}

void dfs(int now)
{
    if(!node[now].f.size())
    {
        cnt[now]=1;
        int *p=new int[cnt[now]+2];
        p[0]=0; p[1]=node[now].val;
        node[node[now].fa].Q.push(p);
        delete[] p;
        return;
    }

    for(int i=0;i<node[now].f.size();i++)
    {
        int id=node[now].f[i];
        cnt[now]=cnt[now]+cnt[id];
    }

    cnt[now]=min(k,cnt[now]);

    int *p=new int[cnt[now]+2];

    p[0]=0;
    for(int i=1;i<=cnt[now];i++) p[i]=-1;

    int id=0;
    while(!node[now].Q.empty())
    {
        int *head=node[now].Q.front();
        node[now].Q.pop();

        for(int j=cnt[now];j>=0;j--)
            for(int s=0;s<=j&&s<=cnt[node[now].f[id]];s++)
                if(head[s]!=-1&&p[j-s]!=-1)
                    p[j]=max(p[j],head[s]+p[j-s]);
        id++;
    }
    p[1]=max(p[1],node[now].val);

    node[node[now].fa].Q.push(p);

    if(now==1)
    {
        if(cnt[1]<k||p[k]==-1) ans=-1;
        else ans=p[k];
    }

    delete[] p;
    return;
}

void work()
{
    dfs(root);
    if(ans==-1) printf("impossible
");
    else printf("%d
",ans);
}

int main()
{
    while(~scanf("%d%d",&n,&k))
    {
        init();
        read();
        work();
    }
    return 0;
}

2D DP 쓰기HDU에서 MLE의UvaLive 넘길 수 있어.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n, k;
int root;
const int maxn = 150000 + 10;
struct Edge
{
    int now;
    int next;
}e[maxn];
int head[maxn];
int cnt[maxn];
int val[maxn];
int dp[maxn][300 + 10];
int q;

void init()
{
    q=0;
    for(int i=1;i<=n;i++) head[i]=-1;
}

void read()
{
    for (int i = 1; i <= n; i++)
    {
        int fa;
        scanf("%d%d", &fa, &val[i]);
        if (!fa) root = i;
        else
        {
            e[q].now=i, e[q].next=head[fa];
            head[fa]=q, q=q+1;
        }
    }
}

void dfs(int now)
{
    cnt[now]=0;
    if (head[now]==-1)
    {
        cnt[now]=1;
        dp[now][1] = val[now];
        return;
    }

    for (int i = head[now]; i!=-1; i=e[i].next)
    {
        int id = e[i].now;
        dfs(id);
        cnt[now]=cnt[now]+cnt[id];
    }

    cnt[now]=min(cnt[now],k);

     for(int i=0;i<=cnt[now];i++) dp[now][i]=-1;
        dp[now][0]=0;

    for (int i = head[now]; i!=-1; i=e[i].next)
    {
        int id = e[i].now;
        for(int j=cnt[now];j>=0;j--)
            for(int s=0;s<=j&&s<=cnt[id];s++)
                if(dp[id][s]!=-1&&dp[now][j-s]!=-1)
                    dp[now][j]=max(dp[now][j],dp[id][s]+dp[now][j-s]);
    }
    dp[now][1]=max(val[now],dp[now][1]);
}

void work()
{
    dfs(root);
    if (cnt[root]<k||dp[root][k] == -1) printf("impossible
");
    else printf("%d
", dp[root][k]);
}

int main()
{
    while (~scanf("%d%d", &n, &k))
    {
        init();
        read();
        work();
    }
    return 0;
}