codeforces #338 div2 B || 615B Longtail Hedgehog

题目链接
题意:给出n个点,m条边,定义一条路径的价值为【路径长度*(路径终点的度)】,求最大价值。
思路:一月份的时候写过一个回溯。。。TLE22了。。。其实也能猜到是dp..但是无奈不会写。然而其实真的不难==
我们枚举路径的终点,dp[i]表示以点i为终点能得到的最长路径长度。

转移方程:dp[i] = max(dp[i],dp[edge[i][j]]+1);

含义是与i点相连的j点是否要将i点加在以j点为路径末尾的路径的终点,使i点成为新的路径终点。

具体看代码

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz