题目描述：
喜欢数学的 wls 最近被萎住了。
现在他一共有1...n这么多数字，取数字 i 会得到 f[i] 的收益。数字之间有些边，对于所有的 i (i != 1)，若 i 为奇数，则 i 与3i+1 之间有边，否则 i 与 i/2 之间有边。如果一条边的两个顶点 xy 都被取了，那么会失去 d[min(x,y)] 的价值。请问 wls 怎么取，才能使得收益最大？
思路：
此题的重点在于发现这是一个树形结构，准确的说是一个森林结构，可以对于前10个数画一下数之间的关系得到，然后就可以对于每颗树进行dp，dp[x][0]表示x这个节点不取的状态，dp[x][1]表示x这个节点取的状态，然后进行dp转移即可。
代码：【代码有点丑...】
#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>#define rep(i,a,b) for(int i = a; i <= b; i++)using namespace std;const int N = 1000;int n;int f[N], d[N];int dp[N][3], vis[N], ans[N], flag[N], wls[N][4];void dfs(int x, int fa, int mark){flag[x] = mark;vis[x] = 1;dp[x][0] = 0, dp[x][1] = f[x];if(x == 1) dp[1][1] = f[1], dp[1][0] = 0;else if(x % 2 == 0){int a = x*2;if(a != fa && a <= n && vis[a] == 0){dfs(a,x,mark);dp[x][0] = max(dp[x][0],max(dp[x][0]+dp[a][1],dp[x][0]+dp[a][0]));dp[x][1] = max(dp[x][1],max(dp[x][1]+dp[a][0],dp[x][1]+dp[a][1]-d[min(a,x)]));}a = x/2;if(a != fa && vis[a] == 0){dfs(a,x,mark);dp[x][0] = max(dp[x][0],max(dp[x][0]+dp[a][1],dp[x][0]+dp[a][0]));dp[x][1] = max(dp[x][1],max(dp[x][1]+dp[a][0],dp[x][1]+dp[a][1]-d[min(a,x)]));}a = x-1;if(a%3 == 0 && a/3 != fa && a != 3 && vis[a/3] == 0 && (a/3)%2==1){a = a/3;dfs(a,x,mark);dp[x][0] = max(dp[x][0],max(dp[x][0]+dp[a][1],dp[x][0]+dp[a][0]));dp[x][1] = max(dp[x][1],max(dp[x][1]+dp[a][0],dp[x][1]+dp[a][1]-d[min(a,x)]));}}else if(x % 2 == 1){int a = 3*x+1;if(a != fa && a <= n && vis[a] == 0){dfs(a,x,mark);dp[x][0] = max(dp[x][0],max(dp[x][0]+dp[a][1],dp[x][0]+dp[a][0]));dp[x][1] = max(dp[x][1],max(dp[x][1]+dp[a][0],dp[x][1]+dp[a][1]-d[min(a,x)]));}a = x-1;if(a%3 == 0 && a/3 != fa && a != 3 && vis[a/3] == 0 && (a/3)%2==1){a = a/3;dfs(a,x,mark);dp[x][0] = max(dp[x][0],max(dp[x][0]+dp[a][1],dp[x][0]+dp[a][0]));dp[x][1] = max(dp[x][1],max(dp[x][1]+dp[a][0],dp[x][1]+dp[a][1]-d[min(a,x)]));}a = x*2;if(a != fa && a <= n && vis[a] == 0){dfs(a,x,mark);dp[x][0] = max(dp[x][0],max(dp[x][0]+dp[a][1],dp[x][0]+dp[a][0]));dp[x][1] = max(dp[x][1],max(dp[x][1]+dp[a][0],dp[x][1]+dp[a][1]-d[min(a,x)]));}}}void solve(){int tot = 0;if(n == 1) printf("%d\n",f[1]);else{rep(i,2,n)if(vis[i] == 0)dfs(i,-1,++tot);// rep(i,1,n){// printf("i:%d,flag:%d\n",i,flag[i]);// }rep(i,1,tot)rep(j,1,n)if(flag[j] == i){if(dp[j][1] > ans[i]){ans[i] = dp[j][1];wls[i][0] = j;wls[i][1] = 1;}if(dp[j][0] > ans[i]){ans[i] = dp[j][0];wls[i][0] = j;wls[i][1] = 0;}// ans[i] = max(ans[i],max(dp[j][1],dp[j][0]));}int maxn = 0;rep(i,1,tot){maxn += ans[i];// printf("%d,%d,ans[i]:%d\n",wls[i][0],wls[i][1],ans[i]);} printf("%d\n",maxn);}}int main(){scanf("%d",&n);rep(i,1,n) scanf("%d",&f[i]);rep(i,1,n) scanf("%d",&d[i]);solve();return 0;}/*201 2 3 3636 5 6 7 8 21 10 11 3242 13 14 15 16 17 28 16 551 2 3212 4 5 6 7 232 9 10 4746 12 4656 14 15 16 122 2121 22 21*/
