CFR 615 B. Longtail Hedgehog ( DP )
Problem - 615B - Codeforces
題意:
給一張不一定連通的圖。求一個序列,使起點至終點都相鄰,且編號遞增,此前提下序列長度和序列末尾節點的度數之乘積最大。
解法:
dp[ i ] : 以 i 節點為末尾的最長序列長度
更新方向顯然是由編號小的節點至大的就行了。
int N, M; vvi G; void init(){ cin >> N >> M; G = vvi( N ); for( int i = 0; i < M; ++i ){ int u, v; cin >> u >> v; if( not ( u < v ) ) swap( u, v ); G[ u - 1 ].emplace_back( v - 1 ); } } vi dp; vi deg; void preprocess(){ dp = vi( N, 1 ); for( int i = 0; i < N; ++i ) for( int v : G[ i ] ) upmax( dp[ v ], dp[ i ] + 1 ); deg = vi( N ); for( int i = 0; i < N; ++i ) for( int v : G[ i ] ) ++deg[ i ], ++deg[ v ]; } void solve(){ ll ans = 0; for( int i = 0; i < N; ++i ) upmax( ans, 1LL * dp[ i ] * deg[ i ] ); cout << ans << endl; }