我愛海洋的题解
记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。
在解题之前提交题解的代码会导致封禁。
作者：
Subtask 1
輸出 \(1\)。（WA 20%）
Subtask 2
可能性不多，手算打表。（WA 20%）
Subtask 1~4
枚舉起點和終點，BFS/DFS 距離，\(O(n^2m)\)。（TLE 80%）
Subtask 1~3
經典的 DP on DAG。因為輸入已經幫你拓樸排序好了，所以連 DFS 都不用，直接 \(dp[i] = max(\{ dp[j] + 1 | \forall j\:connected\:with\:i \land depth[j] < depth[i] \} \cup \{0\})\)，\(i\) 由小到大枚舉。\(O(n)\)。（WA 60%）
Subtask 1~5
Solution 1
先拓樸排序，再套用 subtask 1 \(\sim\) 3 的作法，\(O(n)\)。（AC 100%）
Solution 2
注意到由於此題的特殊性質，可以直接對深度排序來代替拓樸排序，\(O(nlgn)\)。（AC 100%）
Solution 3
直接記憶化 DP，\(O(n)\)。（AC 100%）
標程
C++ 深度排序（by ）
#include<bits/stdc++.h>
using namespace std;
#define maxn 100010
#define pii pair<int,int>
#define F first
#define S second
vector<int> g[maxn];
pii a[maxn];
int dp[maxn];
main()
{
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
int x;scanf("%d",&x);
x=n-x+1;
a[i]=pii(x,i);
}
for(int i=1;i<=m;i++)
{
int x,y;scanf("%d%d",&x,&y);
if(a[x].F>a[y].F)g[x].push_back(y);
else g[y].push_back(x);
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
{
int mx=0,u=a[i].S;
for(int v : g[u])mx=max(mx,dp[v]);
dp[u]=mx+1;
}
int ans=0;
for(int i=1;i<=n;i++)ans=max(ans,dp[i]);
printf("%d\n",ans-1);
return 0;
}
C++ 拓樸排序
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
using namespace std;
const int mod=1e9+7;
const int INF=2147483647;
vector<int> G[100005],vv;
bool vis[100005];
void dfs(int u){
vis[u]=1;
for(int v:G[u]) if(!vis[v]) dfs(v);
vv.emplace_back(u);
}
int a[100005],sz[100005];
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
while(m--){
int x,y;
scanf("%d%d",&x,&y);
if(a[x]<a[y]) G[x].emplace_back(y);
else G[y].emplace_back(x);
}
vv.reserve(n);
for(int i=1;i<=n;i++) if(!vis[i]){
dfs(i);
}
int ans=0;
for(int x:vv){
int ma=0;
for(int y:G[x]) ma=max(ma,sz[y]+1);
sz[x]=ma;
ans=max(ans,ma);
}
printf("%d\n",ans);
return 0;
}
Scala 記憶化 DP（by ）
case class Memo[I <% K, K, O](f: I => O) extends (I => O) {
val cache = collection.mutable.Map.empty[K, O]
override def apply(x: I) = cache getOrElseUpdate (x, f(x))
}
object x005 extends App {
def readL() = io.StdIn.readLine().split(" ").map(_.toInt)
val Array(n, m), depth = readL()
val _g = (1 to m).map(_ => readL())
val g = _g ++ _g.map(_.reverse) groupBy (_(0))
lazy val dp: Memo[Int, Int, Int] = Memo { x =>
1 + g.getOrElse(x, Seq.empty).view
.filter(y => depth(y(1) - 1) > depth(x - 1))
.map(y => dp(y(1)))
.fold(0)(_ max _)
}
println((1 to n).map(x => dp(x)).max - 1)
}
评论