【codeforces Manthan, Codefest 17 C】Helga Hufflepuff's Cup
2024-09-06 12:44:02
【链接】h在这里写链接
【题意】
k是最高级别的分数,最高界别的分数最多只能有x个。
1<=k<=m;
和k相邻的点的分数只能小于k;
n个点的树,问你每个点的分数的安排,方案数%1e9+7
1<=k<=m;
和k相邻的点的分数只能小于k;
n个点的树,问你每个点的分数的安排,方案数%1e9+7
【题解】
设
f[i][j][0];//这棵子树下面有j个最高级别的点,这个点放Top点的方案数
f[i][j][1];//这棵子树下面有j个最高级别的点,这个点放小于等于k-1的点的方案数
f[i][j][2];//这棵子树下面有j个最高级别的点,这个点放大于k的点的方案数
叶子节点
f[i][1][0] = 1;
f[i][0][1] = k-1;
f[i][0][2] = m - k;
然后进行转移
for (int i = limit; i >= 0; i--)//枚举x节点它的重要节点个数
{
//这里的i必须是逆序的,这样才可保证f[x][i-j]访问到的是x这个节点前面
//的儿子的方案数
//显然也必须用3个temp->s0,s1,s2来暂存到这个儿子为止的 f[x][]信息了。
//之后再复制给temp就好
ll s0 = 0, s1 = 0, s2 = 0;
for (int j = 0; j <= i; j++)//枚举y的重要节点个数
{
//x这个节点放重要节点方案
if (i != j) s0 += f[y][j][1] * f[x][i - j][0]%MOD;
//这里的f[x][i-j][0]指的是x这个节点前面的儿子的方案
s0 %= MOD;
//y只能放小于等于k-1的了
s1 += (f[y][j][0] + f[y][j][2] + f[y][j][1])%MOD*f[x][i - j][1]%MOD;
s1 %= MOD;
//x放小于等于k-1的,则y可以放Top点也可以放大于K的点也可以放小于k的
s2 += (f[y][j][1] + f[y][j][2])%MOD* f[x][i - j][2]%MOD;
s2 %= MOD;
//x放大于K的点,y能放大于k以及小于等于k-1的点
}
f[x][i][0] = s0;
f[x][i][1] = s1;
f[x][i][2] = s2;
}
最后对f[1][0..x][0..2]求和
f[i][j][0];//这棵子树下面有j个最高级别的点,这个点放Top点的方案数
f[i][j][1];//这棵子树下面有j个最高级别的点,这个点放小于等于k-1的点的方案数
f[i][j][2];//这棵子树下面有j个最高级别的点,这个点放大于k的点的方案数
叶子节点
f[i][1][0] = 1;
f[i][0][1] = k-1;
f[i][0][2] = m - k;
然后进行转移
for (int i = limit; i >= 0; i--)//枚举x节点它的重要节点个数
{
//这里的i必须是逆序的,这样才可保证f[x][i-j]访问到的是x这个节点前面
//的儿子的方案数
//显然也必须用3个temp->s0,s1,s2来暂存到这个儿子为止的 f[x][]信息了。
//之后再复制给temp就好
ll s0 = 0, s1 = 0, s2 = 0;
for (int j = 0; j <= i; j++)//枚举y的重要节点个数
{
//x这个节点放重要节点方案
if (i != j) s0 += f[y][j][1] * f[x][i - j][0]%MOD;
//这里的f[x][i-j][0]指的是x这个节点前面的儿子的方案
s0 %= MOD;
//y只能放小于等于k-1的了
s1 += (f[y][j][0] + f[y][j][2] + f[y][j][1])%MOD*f[x][i - j][1]%MOD;
s1 %= MOD;
//x放小于等于k-1的,则y可以放Top点也可以放大于K的点也可以放小于k的
s2 += (f[y][j][1] + f[y][j][2])%MOD* f[x][i - j][2]%MOD;
s2 %= MOD;
//x放大于K的点,y能放大于k以及小于等于k-1的点
}
f[x][i][0] = s0;
f[x][i][1] = s1;
f[x][i][2] = s2;
}
最后对f[1][0..x][0..2]求和
【错的次数】
0
【反思】
根据区间写DP的状态。
这个思路挺好的。
枚举父亲和儿子节点的重要点,有点像选课那题。
用到了01背包去掉第一维的思想.
暂存到另外一个数组,再赋值回去。
防止造成错乱,维护前缀最优~
【代码】
#include <bits/stdc++.h>
#define ll long long
using namespace std; const int N = 1e5;
const int MOD = 1e9 + 7;
const int X = 10; int n, m,k,limit;
ll f[N + 10][X+5][3];
vector<int> g[N+10]; void dfs(int x, int fa)
{
//叶子节点
f[x][1][0] = 1;
f[x][0][1] = k - 1;
f[x][0][2] = m - k;
for (int y : g[x])
{
if (y == fa) continue;
dfs(y, x);
//前面的儿子选了j个,状态为3的方案数
//f[x][j][3]
for (int i = limit; i >= 0; i--)//枚举x节点它的重要节点个数
{
ll s0 = 0, s1 = 0, s2 = 0;
for (int j = 0; j <= i; j++)//枚举y的重要节点个数
{
//x这个节点放重要节点方案
if (i != j) s0 += f[y][j][1] * f[x][i - j][0]%MOD;
s0 %= MOD;
//y只能放小于等于k-1的了 s1 += (f[y][j][0] + f[y][j][2] + f[y][j][1])%MOD*f[x][i - j][1]%MOD;
s1 %= MOD;
//x放小于等于k-1的,则y可以放Top点也可以放大于K的点也可以放小于k的 s2 += (f[y][j][1] + f[y][j][2])%MOD* f[x][i - j][2]%MOD;
s2 %= MOD;
//x放大于K的点,y能放大于k以及小于等于k-1的点
}
f[x][i][0] = s0;
f[x][i][1] = s1;
f[x][i][2] = s2;
}
}
} int main()
{
//freopen("F:\\rush.txt", "r", stdin);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n - 1; i++)
{
int x, y;
scanf("%d%d", &x, &y);
g[x].push_back(y), g[y].push_back(x);
}
scanf("%d%d", &k, &limit);
dfs(1, 0);
ll ans = 0;
for (int i = 0; i <= limit; i++)
{
for (int j = 0; j < 3; j++)
{
ans = ans + f[1][i][j];
ans %= MOD;
}
}
printf("%lld\n", ans);
return 0;
}
最新文章
- AnyCAD.NET C#开发CAD软件实践(一)
- 配置管理服务diamond和disconf横向对比
- innodb的锁
- 演示get、post请求如何算sn,算得sn如何使用
- lca 最近公共祖先
- Asp.Net 构架(Http Handler 介绍) - Part.2
- Android 编程下 Activity 的创建和应用退出时的销毁
- Mysql,zip格式安装、修改密码、建库
- Spring+MyBatis+SpringMvc整合Demo
- ArcGIS 网络分析[2.1] 最短路径
- Powershell:关于hashtable你想知道的一切
- Vue-异步组件
- 思路:controller层:后台如何取值 前端如何给name赋值 例如是id赋值还是自己随意定义
- Codeforces 1136D - Nastya Is Buying Lunch - [贪心+链表+map]
- 浅谈IIS 和 asp.net的应用之间的关系
- linux搭建smb、挂载smb、Windows共享
- [leetcode]Add Binary @ Python
- tomcat默认密码,admin,manager密码需要自己设置,tomcat-users.xml
- 003-spring cloud gateway-概述、Route模型、网关初始化配置过程、基本原理
- Mysql -Linux系统下安装指南
热门文章
- linux系统下重要的分区及其作用
- javascript的Touch事件
- PhpStorm中terminal窗口字体修改
- mysql不创建表 <;property name=";hbm2ddl.auto";>;update<;/property>; 无效
- MATLAB---fopen、fprintf函数
- 2019-7-15-win10-uwp-在笔迹开始书写拿到书写移动事件
- K8s 学习者绝对不能错过的最全知识图谱(内含 56个知识点链接)
- TZ_10_spring-AOP日志处理
- 玩转webpack之webpack的基本知识
- C++使用stringstream分割字符串