首页 > 代码库 > POJ 1155 - TELE
POJ 1155 - TELE
树上背包,说实话写起来很难受。看到别人写的代码时间都那么短,实在是自愧不如。
#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\n", 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 |
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。