POJ 1155

树上背包，说实话写起来很难受。看到别人写的代码时间都那么短，实在是自愧不如。

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

#define MAXV        (3000)
#define MAXE        (MAXV - 1)

int Vefw[MAXE], Veh[MAXV], Vecst[MAXE], Vet[MAXE], Veptr;

int N, M;

#define addedge(s,t,c)    ({
    Vefw[Veptr] = Veh[s], Vet[Veptr] = t, Vecst[Veptr] = c;    
    Veh[s] = ++Veptr;})

int dp[MAXV][MAXV];

int solve_user(int s)
{
    dp[s][0] = 0;
    dp[s][1] = Veh[s];
    return 1;
}

extern int (*solve[])(int);

int solve_relay(int s)
{
    dp[s][0] = 0;
    int Vsum = 0;
    for(int e = Veh[s]; e; e = Vefw[e]) {
        int t = Vet[--e];
        int Vtsum = solve[t < N-M](t);

        for(int i = Vsum + Vtsum; i > 0; --i) {
            for(int j = 1; j<=Vtsum; ++j) {
                if (i-j < 0) break;
                if (dp[s][i-j] + dp[t][j] - Vecst[e] > dp[s][i])
                    dp[s][i] = dp[s][i-j] + dp[t][j] - Vecst[e];
            }
        }
        for(int i = Vtsum; i>0; --i)
            if (dp[s][i] < dp[t][i] - Vecst[e])
                dp[s][i] = dp[t][i] - Vecst[e];
        Vsum += Vtsum;
    }
    return Vsum;
}

int (*solve[2])(int) = {
    solve_user,
    solve_relay
};

int main(void)
{
//    freopen("poj1155.txt", "r", stdin);
    memset(dp, 0x3f + 0x80, sizeof(dp));

    scanf("%d%d", &N, &M);
    int s;
    for(s=0; s<N-M; ++s) {
        int K;
        scanf("%d", &K);
        for(int j=0; j<K; ++j) {
            int t, c;
            scanf("%d%d", &t, &c); --t;
            addedge(s, t, c);
        }
    }
    for(; s<N; ++s)
        scanf("%d", &Veh[s]);

    for(s = solve[1/*s < N-M */](0); s-- ; )
        if (dp[0][s] >= 0) break;

    printf("%d
", s);
    return 0;
}

1155	Accepted	35680K	266MS	G++	1487B	2014-05-10 18:45:16
1155	Accepted	35704K	219MS	G++	1540B	2014-05-10 18:42:04