当前位置： 移动技术网 > 移动技术>移动开发>IOS > Codeforces486 D. Valid Sets（树形dp，去重技巧）

Codeforces486 D. Valid Sets（树形dp，去重技巧）

2020年08月14日  | 移动技术网移动技术  | 我要评论

题意：

给定n个点的树，每个点有点权a(i)，
给定整数D，
定义合法连通块为：
连通块中最大点权-连通块中最小点权<=D

问有多少种合法连通块，答案对1e9+7取模

数据范围：n<=2000，a(i)<=2000

解法：

容易想到枚举每个点作为连通块的点权最小值，且作为树的根，然后进行树形dp
令d[i]为点i的方案数，根据乘法原理：d[x]=d[x]*(d[v]+1)，（转移需要满足点权在合法范围内）
复杂度O(n2)

但是会有重复的情况：
如果a(p1)=x,a(p2)=x，以p1为根的的时候dp到了p2，那么以p2为根的时候也会dp到p1，
这样就重复了，
解决方法：
当出现点v与当前根rt的点权相同的时候，规定一个唯一方向，例如：
当出现a(v)=a(rt)的时候，只有当rt>v的时候(这里比较的是编号大小)，才能进行dp
这样能保证只dp一次，巧妙的去重了。

code：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxm=2e3+5;
const int mod=1e9+7;
vector<int>g[maxm];
int a[maxm];
int D,n;
//
int d[maxm];
int L,R;
int rt;
void dfs(int x,int fa){
    d[x]=1;
    for(int v:g[x]){
        if(v==fa||a[v]<L||a[v]>R)continue;
        if(a[v]==a[rt]){
            if(v>rt)continue;
        }
        dfs(v,x);
        d[x]=d[x]*(d[v]+1)%mod;
    }
}
//
signed main(){
    ios::sync_with_stdio(0);
    cin>>D>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<n;i++){
        int a,b;cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int ans=0;
    for(int i=1;i<=n;i++){//枚举每个点作为连通块点权最小值
        L=a[i],R=a[i]+D;
        rt=i;
        dfs(i,i);
        ans=(ans+d[i])%mod;
    }
    cout<<ans<<endl;
    return 0;
}

本文地址：https://blog.csdn.net/weixin_44178736/article/details/107936536

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网