[LOJ #2473] [九省联考2018] 秘密袭击coat

浅浅的花香味﹌ 2021-09-30 12:06 178阅读 0赞

## 题目链接 ##

[洛谷][Link 1].

[LOJ][],LOJ机子是真的快

## Solution ##

我直接上暴力了...\\(O(n^2k)\\)洛谷要\\(O2\\)才能过...loj平均单点一秒...

直接枚举每个点为第\\(k\\)大的点，然后\\(dp\\)出方案数统计答案就好了。

\\(f\[i\]\[j\]\\)\\(dfs\\)下去的时候表示考虑到\\(i\\)，有\\(j\\)个大于\\(i\\)的点的方案数，此时没有考虑儿子。

然后回溯的时候从叶子节点把儿子的影响加回来就好了。

#include<bits/stdc++.h> using namespace std; void read(int &x) { x=0;int f=1;char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f; } void print(int x) { if(x<0) putchar('-'),x=-x; if(!x) return ;print(x/10),putchar(x%10+48); } void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');} #define lf double #define ll long long const int maxn = 1700+10; const int inf = 1e9; const lf eps = 1e-8; const int mod = 64123; int val[maxn],f[maxn][maxn],head[maxn],tot,n,k,w,ans,rt; struct edge{int to,nxt;}e[maxn<<1]; void Add(int u,int v) {e[++tot]=(edge){v,head[u]},head[u]=tot;} void ins(int u,int v) {Add(u,v),Add(v,u);} int add(int x,int y) {return x+y>mod?x+y-mod:x+y;} void dfs(int x,int fa) { if(val[x]>val[rt]||(val[x]==val[rt]&&x>rt)) for(int i=2;i<=k;i++) f[x][i]=add(f[x][i],f[fa][i-1]); else for(int i=1;i<=k;i++) f[x][i]=add(f[x][i],f[fa][i]); for(int i=head[x];i;i=e[i].nxt) if(e[i].to!=fa) dfs(e[i].to,x); if(fa) for(int i=1;i<=k;i++) f[fa][i]=add(f[fa][i],f[x][i]); } int main() { read(n),read(k),read(w); for(int i=1;i<=n;i++) read(val[i]); for(int i=1,x,y;i<n;i++) read(x),read(y),ins(x,y); for(int i=1;i<=n;i++) { int cnt=1;rt=i; for(int j=1;j<=n;j++) cnt+=val[j]>val[i]||(val[j]==val[i]&&j>i); if(cnt<k) continue; for(int j=1;j<=n;j++) for(int t=0;t<=k;t++) f[j][t]=0; f[i][1]=1;for(int j=head[i];j;j=e[j].nxt) dfs(e[j].to,i); ans=add(ans,1ll*f[i][k]*val[i]%mod); } write(ans); return 0; }

转载于:https://www.cnblogs.com/hbyer/p/10603901.html

[Link 1]: https://www.luogu.org/problemnew/show/P4365
[LOJ]: https://loj.ac/problem/2473