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}