bzoj5250 [2018多省省队联测]秘密袭击

博主蒟蒻，目前还不会动态dp，所以下面说的是一个并不优秀的暴力，我会补的！

我们考虑按权值从大到小依次点亮每个点，相同权值可以同时点亮，每次点亮后，我们进行一次树形背包。

处理出$f[i][j]$表示i的子树中有j个亮点的方案数，然后就AC了。

有两个小优化，一个是将背包的枚举上限设为min(size[x],K)，此处size[x]为子树中点亮的点的的个数。

还有就是我们可以把大于K的dp值都和K合并到一起，因为我们需要的是所有大于等于K的方案数。

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #include <cmath>

 #define N 1700

 #define mod 64123

 using namespace std;

 int e=,head[N];

 struct edge{

     int v,next;

 }ed[N<<];

 void add(int u,int v){

     ed[e].v=v;

     ed[e].next=head[u];

     head[u]=e++;

 }

 int n,m,K,a[N],pp[N];

 int f[N][N],g[N],size[N],vis[N],ans,sum,last;

 bool cmp(int a,int b){return ::a[a]>::a[b];}

 void dfs(int x,int fa){

     for(int i=;i<=K;i++)f[x][i]=;

     size[x]=vis[x];f[x][size[x]]=;

     for(int i=head[x];i;i=ed[i].next){

         int v=ed[i].v;

         if(v==fa)continue;

         dfs(v,x);

         int up1=min(size[x],K),up2=min(size[v],K);

         for(int j=min(up1+up2,K);~j;j--)g[j]=;

         for(int j=up1;~j;j--)

             for(int k=up2;~k;k--)

                 (g[min(j+k,K)]+=1ll*f[x][j]*f[v][k]%mod)%=mod;

         size[x]+=size[v];

         up1=min(size[x],K);

         for(int j=;j<=up1;j++)f[x][j]=g[j];

     }

     f[x][]++;

     (sum+=f[x][K])%=mod;

 }

 int main(){

     scanf("%d%d%d",&n,&K,&m);

     for(int i=;i<=n;i++){

         scanf("%d",&a[i]);

         pp[i]=i;

     }

     sort(pp+,pp+n+,cmp);

     for(int i=,u,v;i<n;i++){

         scanf("%d%d",&u,&v);

         add(u,v);add(v,u);

     }

     for(int i=;i<=n;){

         do vis[pp[i]]=,i++;

         while(i<=n&&a[pp[i]]==a[pp[i-]]);

         if(i<K)continue;

         sum=;dfs(,);

         (ans+=1ll*(sum-last+mod)*a[pp[i-]]%mod)%=mod;

         last=sum;

     }

     printf("%d\n",ans);

     return ;

 }

巴特西

bzoj5250 [2018多省省队联测]秘密袭击

最新文章

热门文章