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点成为新的路径终点。
具体看代码
/* ***********************************************
Author :111qqz
Created Time :2016年01月08日 星期五 21时55分26秒
File Name :code/cf/#338/B.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=2E5+7;
7int n,m;
8vector<int>edge[N];
9LL ans;
10LL cur;
11LL dp[N];
1int main()
2{
3 #ifndef ONLINE_JUDGE
4 freopen("code/in.txt","r",stdin);
5 #endif
6 cin>>n>>m;
7 for ( int i = 0 ; i < m ; i ++)
8 {
9 int x,y;
10 scanf("%d %d",&x,&y);
11 edge[x].push_back(y);
12 edge[y].push_back(x);
13 }
1 for ( int i = 1 ; i <= n ; i++)
2 {
3 dp[i] = 1;
4 for (int j = 0 ; j < int(edge[i].size()) ; j++)
5 {
6 int v = edge[i][j];
7 dp[i] = max(dp[i],dp[v]+1);
8 }
9 ans = max(ans,LL(edge[i].size())*dp[i]);
10 }
11 cout<<ans<<endl;
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}