@OceanEye4年前
11/15
13:21
HDU1520
树形DP水题，有坑，要认真看题目
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include <cstdio> #include <algorithm> #include <cstring> #include <cstdlib> using namespace std; #define N 6010 struct Tedge { int to,nxt; Tedge():to(0),nxt(0){} Tedge(int _,int __):to(_),nxt(__){} }edge[N]; int etot,fst[N]; inline void add_e(int a,int b) { edge[++etot]=Tedge(b,fst[a]); fst[a]=etot; } int n,a[N],in[N],root; int dp[N][2]; #define NXT edge[i].nxt #define TO edge[i].to void dfs(int x) { for(int i=fst[x];i;i=NXT) { dfs(TO); dp[x][0]+=max(dp[TO][0],dp[TO][1]); dp[x][1]+=dp[TO][0]; } dp[x][1]+=a[x]; } int main() { while(~scanf("%d",&n)) { if(!n) break; etot=0; for(int i=1;i<=n;++i) scanf("%d",a+i),in[i]=dp[i][0]=dp[i][1]=0,fst[i]=0; for(int i=1,_,__;i<n;++i) { scanf("%d %d",&_,&__); add_e(__,_); ++in[_]; } for(int i=1;i<=n;++i) if(!in[i]) { root=i; break; } dfs(root); printf("%d\n",max(dp[root][0],dp[root][1])); scanf("%d",&n); scanf("%d",&n); } return 0; } |
URAL1018
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 |
#include <cstdio> #include <algorithm> #include <cstring> #include <cstdlib> #include <cmath> #include <iostream> #include <bits/stdc++.h> #define ll long long #define INF 1000000000 #define p(x) ('0'<=x&&x<='9') #define For(i,a,b) for(int i=a;i<=b;++i) #define Rev(i,a,b) for(int i=a;i>=b;--i) char cc; int C; template <class T> void read( T &x ) { x=0; cc=getchar(); C=1; while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } #undef p #define pb push_back #define pq priority_queue using namespace std; //dp[i][j] = max for (i=0 -> j)( dp[c1][i]+ dp[c2][j-i]) int n,q; #define N 110 struct Tedge { int to,val,nxt; Tedge():to(0),val(0),nxt(0){} Tedge(int _,int __,int ___):to(_),val(__),nxt(___){} }edge[N<<1]; int fst[N],etot; inline void add_e(const int &a,const int &b,const int &c) { edge[++etot]=Tedge(b,c,fst[a]); fst[a]=etot; edge[++etot]=Tedge(a,c,fst[b]); fst[b]=etot; } void init() { int a,b,c; read(n); read(q); For(i,1,n-1) { read(a); read(b); read(c); add_e(a,b,c); } } #define TO edge[i].to #define VAL edge[i].val #define NXT edge[i].nxt #define FA fa[x] int fa[N]; ll dp[N][N]; void dfs(int x) { vector <int> children; vector <int> cost; for(int i=fst[x];i;i=NXT) { if(TO==FA) continue; fa[TO]=x; dfs(TO); children.pb(TO); cost.pb(VAL); } if(!children.size()) return; For(_,0,children.size()-1) if(_==0) For(i,1,q) dp[x][i]=dp[children[0]][i-1]+cost[0]; else Rev(i,q,1) { ll cur=dp[x][i-1]+cost[_]; For(j,1,int(i)-1) { dp[x][i]=max(dp[x][i],dp[x][i-j-1]+dp[children[_]][j]+cost[_]); } dp[x][i]=max(dp[x][i],cur); } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); srand(time(NULL)); #ifdef LOCAL freopen("/Users/antontsypko/tsypko/input.txt", "r", stdin); #endif init(); dfs(1); ll ans=0; For(i,1,q) ans=max(ans,dp[1][i]); printf("%lld\n",ans); return 0; } |
HDU2196
这道题做法很多，可以两遍DFS，可以找最长链【重链？】，可以点分治，这次写的DFS
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 |
#include <cstdio> #include <algorithm> #include <cstring> #include <cstdlib> #include <cmath> #include <iostream> #include <bits/stdc++.h> #define ll long long #define INF 1000000000 #define p(x) ('0'<=x&&x<='9') #define For(i,a,b) for(int i=a;i<=b;++i) #define Rev(i,a,b) for(int i=a;i>=b;--i) char cc; int C; template <class T> void read( T &x ) { x=0; cc=getchar(); C=1; while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } #undef p #define pb push_back #define pq priority_queue using namespace std; #define N 10010 int n; struct Tedge { int to,val,nxt; Tedge():to(0),val(0),nxt(0){} Tedge(int _,int __,int ___):to(_),val(__),nxt(___){} }edge[N<<1]; int fst[N],etot; inline void add_e(int a,int b,int c) { edge[++etot]=Tedge(b,c,fst[a]); fst[a]=etot; edge[++etot]=Tedge(a,c,fst[b]); fst[b]=etot; } #define NXT edge[i].nxt #define TO edge[i].to #define VAL edge[i].val #define FA fa[x] int fa[N]; ll depth[N],mxdep[N],ans[N]; ll dfs1(int x) { mxdep[x]=depth[x]; for(int i=fst[x];i;i=NXT) { if(TO==FA) continue; depth[TO]=depth[x]+VAL; fa[TO]=x; mxdep[x]=max(mxdep[x],dfs1(TO)); } return mxdep[x]; } // same dist // LCS // C1 C2 multiset<ll ,greater <ll> > upper; multiset<ll ,greater <ll> > :: iterator it; void print(int x) { printf("%d : ",x); for(it=upper.begin();it!=upper.end();++it) printf("%lld ",*it); puts(""); } void dfs2(int x) { for(int i=fst[x];i;i=NXT) if(TO!=fa[x])upper.insert(mxdep[TO]-(depth[x]<<1)); // print(x); it=upper.begin(); ans[x]=*it+depth[x]; for(int i=fst[x];i;i=NXT) if(TO!=fa[x]) { it=upper.find(mxdep[TO]-(depth[x]<<1)); upper.erase(it); dfs2(TO); upper.insert(mxdep[TO]-(depth[x]<<1)); // print(x); } for(int i=fst[x];i;i=NXT) if(TO!=fa[x]) { it=upper.find(mxdep[TO]-(depth[x]<<1)); upper.erase(it); } } void init() { etot=0; memset(fst,0,sizeof(fst)); memset(fa,0,sizeof(fa)); memset(mxdep,0,sizeof(mxdep)); upper.clear(); upper.insert(0); int a,b; For(i,1,n-1) { read(a); read(b); add_e(i+1,a,b); } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); srand(time(NULL)); #ifdef LOCAL freopen("/Users/antontsypko/tsypko/input.txt", "r", stdin); #endif while(~scanf("%d",&n)) { init(); dfs1(1); dfs2(1); For(i,1,n) printf("%lld\n",ans[i]); } return 0; } |