msc的宠物

第一行两个整数n和k，表示宠物的数量和至多去掉的连接关系数量。
第二行n个整数a[i]，第i个数表示宠物i的评估值。
接下来n-1行，每行两个正整数u,v，表示宠物u和宠物v的家之间有连接关系。

C++14(g++5.4) 解法, 执行用时: 126ms, 内存消耗: 4396K, 提交时间: 2020-08-18 20:17:35

#include<bits/stdc++.h>
#define pb push_back
#define sc(x) scanf("%d",&x)
#define sll(x) scanf("%lld",&x)
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int maxn = 1e3+10;
vector<int> to[maxn];
int n, k, a[maxn], f[maxn][maxn], g[maxn];
 
void dfs(int u, int fa, LL x){
	for(int i=1;i<=n;i++) f[u][i]=(a[u]>=a[i]&&a[u]<=a[i]+x)?0:INF;
	for(int v: to[u]) if(v!=fa){
		dfs(v,u,x);
		for(int i=1;i<=n;i++) f[u][i]+=min(f[v][i],g[v]+1);
	}
	for(int i=1;i<=n;i++)g[u]=min(g[u],f[u][i]);
}
int check(LL x){
	memset(g,INF,sizeof(g));
	dfs(1,1,x);
	return g[1];
}
 
int main(){
	sc(n); sc(k);
	for(int i=1;i<=n;i++) sc(a[i]);
	for(int i=1;i<n;i++){
		int u,v; sc(u); sc(v);
		to[u].pb(v); to[v].pb(u);
	}
	LL L=-1,R=INF*2;
	while(L+1<R){
		LL mid=(L+R)>>1;
		if(check(mid)>k) L=mid;
		else R=mid;
	}
	printf("%lld\n",R);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 90ms, 内存消耗: 4384K, 提交时间: 2020-08-20 10:00:46

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e3+5,inf=0x3f3f3f3f;
int dp[maxn][maxn],ans[maxn],n,k;
ll a[maxn];
vector<int>e[maxn];
void link(int u,int v)
{	return e[u].push_back(v),e[v].push_back(u); }
void dfs(int u,int f,int dif)
{
	for(int i=1;i<=n;i++)
		dp[u][i]=a[i]<=a[u]&&a[u]<=a[i]+dif?0:inf;
	for(int v:e[u]) if(v!=f)
	{
		dfs(v,u,dif);
		for(int i=1;i<=n;i++)
			dp[u][i]+=min(dp[v][i],ans[v]+1);
	}
	ans[u]=inf;
	for(int i=1;i<=n;i++)
		ans[u]=min(ans[u],dp[u][i]);
}
bool check(int mval)
{
	dfs(1,0,mval);
	return ans[1]<=k;
}
int main()
{
	int u,v;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	for(int i=1;i<n;i++)
		scanf("%d%d",&u,&v),link(u,v);
	ll l=0,r=2e9;
	while(l<=r)
	{
		ll mid=(l+r)>>1;
		if(check(mid)) r=mid-1;
		else l=mid+1;
	}
	printf("%d\n",l);
}

详情