美文网首页工作生活
[动态规划] SEUOJ103 排列组合

[动态规划] SEUOJ103 排列组合

作者: kinoud | 来源:发表于2019-07-02 18:11 被阅读0次

初始有一张n个结点没有边的空图,有m次加边或减边的操作,对于每一次操作完成后,求出选择k(k=1,2,...,n/2)条无公共端点的边的方案数(对于两点间的重边,计为不同的方案).
n<=10 m<=3e5
题目链接: https://oj.seucpc.club/problem/103

解法

首先分析一下加减边的影响.设fk(G)表示在G这张图里选取k条边的方案数.那么有f_k(G+(u,v))=f_k(G)+f_k(G-u-v)G+(u,v)是图G加上边(u,v),G-u-v是图G去掉点u和点v.此外还有f_k(G-(u,v))=f_k(G)-f_k(G-u-v)
我们看到无论是加边还是减边,关键一项都是fk(G-u-v).
接下来设计动态规划方法.
设dp(S)= \left\{\begin{align} 所选边覆盖S集中所有点的方案数& &|S|为偶 \\ 0& &|S|为奇 \end{align}\right.
设ans[k]为对于当前图,选择k条边的方案数.
则有
ans(k)=\sum_{|S_i|/2=k}{dp(S_i)}
状态转移为
\begin{align} &加边(u,v)&new\_dp(S+u+v)=dp(S+u+v)+dp(S) \\ &减边(u,v)&new\_dp(S+u+v)=dp(S+u+v)-dp(S) \end{align}
上面这些方程通过分类讨论"方案中是否含有边(u,v)"即可得到.
每次加减边操作后,都按照状态转移方程更新一遍dp数组,并同时计算fk(G-u-v),方法为
f_k(G-u-v)=\sum_{|S_i|/2=k}{dp(S_i)}

如此问题便可得到解决.

相关文章

  • [动态规划] SEUOJ103 排列组合

    初始有一张n个结点没有边的空图,有m次加边或减边的操作,对于每一次操作完成后,求出选择k(k=1,2,...,n/...

  • LeetCode 477 Total Hamming Dista

    LeetCode 排列组合 题目汇总LeetCode 数字 题目汇总LeetCode 动态规划 题目分类汇总干货！...

  • LeetCode 473 Matchsticks to Squa

    LeetCode 排列组合 题目汇总LeetCode 数字 题目汇总LeetCode 动态规划 题目分类汇总干货！...

  • LeetCode 401 Binary Watch

    LeetCode 排列组合 题目汇总LeetCode 数字 题目汇总LeetCode 动态规划 题目分类汇总干货！...

  • LeetCode 461 Hamming Distance

    LeetCode 排列组合 题目汇总LeetCode 数字 题目汇总LeetCode 动态规划 题目分类汇总干货！...

  • 回溯算法

    【回溯算法】在 最优解、排列组合、解空间搜素 中存在典型应用 【动态规划】和【贪心算法】都要求 无后效性，即 子问...

  • 求组合数

    排列组合是经常遇到的问题，本篇文章想跟大家探讨一下，对于给定的，我们该如何去求组合数。 方法一：递归（动态规划） ...

  • Algorithm进阶计划 -- 动态规划（上）

    动态规划动态规划的基本原理动态规划的运用 1. 动态规划的基本原理 动态规划（Dynamic Programmi...

  • 4. 动态规划算法

    1. 动态规划算法总结2. 漫画：什么是动态规划？3.算法之动态规划4. 动态规划-算法

  • 动态规划 Dynamic Programming

    从运筹学和算法的角度综合介绍动态规划 算法分类总结动态规划与静态规划的关系浅析静态规划和动态规划动态规划解非线性规...

网友评论

    本文标题：[动态规划] SEUOJ103 排列组合

    本文链接：https://www.haomeiwen.com/subject/ndpthctx.html

    延伸阅读

    深度阅读

    • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

    栏目导航

    热点阅读

    工作生活

    关于我们|服务条款|联系我们|[动态规划] SEUOJ103 排列组合|投稿指南|网站地图|RSS订阅|排版工具|手机版

    提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

    Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

    备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

    本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

    所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！