首页 > 其他 > 详细

1293E. Xenon's Attack on the Gangs (树形DP)

时间:2020-02-29 18:28:55      阅读:72      评论:0      收藏:0      [点我收藏+]

题目:传送门 

思路:边权是任意填的。 包含0边(边权为0)的树链的mes值至少为1。换言之,0边为这些树链增加了1点的贡献,而1边(边权为1)必须与0边在一条链才能增加贡献,2边必须与1、0边在一条链才能增加贡献。而3、1、0构成一条链的mes为2,与 0、1构成一条链的mes相同,可见 在下图3边 是对答案没有贡献的;

技术分享图片

 

因此可以枚举所有树链从外到内 进行填边(外大内小),用二维的dp可以求出最优解;

思路参考于:传送门

技术分享图片
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 typedef pair<int,int> pii;
 5 typedef pair<double,double> pdd;
 6 const int N=3e3+5;
 7 const LL inf=3e16;
 8 const int mod=1e9+7;
 9 const double eps=1e-9;
10 const long double pi=acos(-1.0L);
11 #define ls (i<<1)
12 #define rs (i<<1|1)
13 #define fi first
14 #define se second
15 #define pb push_back
16 #define mk make_pair
17 #define mem(a,b) memset(a,b,sizeof(a))
18 LL read()
19 {
20     LL x=0,t=1;
21     char ch;
22     while(!isdigit(ch=getchar())) if(ch==-) t=-1;
23     while(isdigit(ch)){ x=10*x+ch-0; ch=getchar(); }
24     return x*t;
25 }
26 struct edge
27 {
28     int to,next;
29     edge(){}
30     edge(int tt,int nn)
31     {
32         to=tt; next=nn;
33     }
34 }e[N<<1];
35 LL head[N],tot,cnt[N][N],f[N][N],dp[N][N];
36 void add(int from,int to)
37 {
38     e[++tot]=edge(to,head[from]);
39     head[from]=tot;
40 }
41 void dfs(int u,int pre,int r)
42 {
43     f[r][u]=pre;
44     cnt[r][u]=1;
45     for(int i=head[u];i;i=e[i].next)
46     {
47         int v=e[i].to;
48         if(v==pre) continue;
49         dfs(v,u,r);
50         cnt[r][u]+=cnt[r][v];
51     }
52 }
53 LL DP(int x,int y)
54 {
55     if(x==y) return 0;
56     if(dp[x][y]!=-1) return dp[x][y];
57     dp[x][y]=cnt[y][x]*cnt[x][y]+max(DP(f[y][x],y),DP(x,f[x][y]));
58     return dp[x][y];
59 }
60 int main()
61 {
62     int n=read();
63     mem(dp,-1);
64     for(int i=1;i<n;i++)
65     {
66         int x=read(),y=read();
67         add(x,y);
68         add(y,x);
69     }
70     for(int i=1;i<=n;i++)
71         dfs(i,0,i);
72     LL ans=0;
73     for(int i=1;i<=n;i++)
74         for(int j=1;j<=n;j++)
75             ans=max(ans,DP(i,j));
76     printf("%lld\n",ans);
77     return 0;
78 }
AC代码

 

1293E. Xenon's Attack on the Gangs (树形DP)

原文:https://www.cnblogs.com/DeepJay/p/12384373.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!