【2022 省选训练赛 Contest 06 B】stat(DP)
2022/2/25 23:21:52
本文主要是介绍【2022 省选训练赛 Contest 06 B】stat(DP),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
stat
题目链接:2022 省选训练赛 Contest 06 B
题目大意
问你有多少对长度为 n 的排列的分数大于等于 k。
两个排列的分数是它们每一位取最大值的和。
思路
考虑固定一个排列按顺序,然后每个跟另外一个匹配,然后答案乘上排列的种数。
然后因为是最大值考虑从大往小 DP:
可以考虑每个数要贡献多少次(\(2,1,0\) 三种可能)
那如果你不当最大值,前面肯定要一个比它大的挡住,所以我们可以这样 DP:
\(f_{i,j,k}\) 为当前到位置 \(i\),前面能拿来挡的有 \(j\) 个,然后当前的分数是 \(k\)。
然后你就分三种情况转:
\(0\) 次:那两边都要被挡住,对面的数组各自都要选一个拿出来,所以要乘上 \(j*j\);然后挡的位置少了一个。
\(1\) 次:那要选一边挡住,或者它们两个自己配对,所以是 \(j+j+1\);能挡的位置其实每边,毕竟你少了一个有多了一个相当于没边。
\(2\) 次:不用挡;能拿来挡的位置多了一个。
代码
#include<cstdio> #define ll long long #define mo 1000000007 using namespace std; int n, k; ll f[72][72][5001]; int main() { scanf("%d %d", &n, &k); f[n + 1][0][0] = 1; for (int i = n + 1; i >= 2; i--) { for (int j = 0; j <= n - i + 1; j++) for (int k = 0; k <= 5000; k++) if (f[i][j][k]) { (f[i - 1][j + 1][k + (i - 1) + (i - 1)] += f[i][j][k]) %= mo; (f[i - 1][j][k + (i - 1)] += f[i][j][k] * (j + j + 1) % mo) %= mo; if (j) (f[i - 1][j - 1][k] += f[i][j][k] * j % mo * j % mo) %= mo; } } ll ans = 0; for (int i = k; i <= 5000; i++) (ans += f[1][0][i]) %= mo; for (int i = 1; i <= n; i++) ans = ans * i % mo; printf("%lld", ans); return 0; }
这篇关于【2022 省选训练赛 Contest 06 B】stat(DP)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-29Elasticsearch慢查询日志配置
- 2024-05-29揭秘华为如此多成功项目的产品关键——Charter模板
- 2024-05-29海外IDC业务拓展的7大挑战
- 2024-05-29InLine Chat功能优化对标Github Copilot,CodeGeeX带来更高效、更直观的编程体验!
- 2024-05-29CodeGeeX 智能编程助手 6 项功能升级,在Visual Studio插件市场霸榜2周!
- 2024-05-29AutoMQ 生态集成 Apache Doris
- 2024-05-292024年IDC行业的深度挖掘:机遇、挑战与未来展望
- 2024-05-29五款扩展组件齐发 —— Volcano、Keda、Crane-scheduler 等,邀你体验
- 2024-05-29AutoMQ 对象存储数据高效组织的秘密: Compaction
- 2024-05-29活动预告|来 GIAC 大会听大数据降本利器:AutoMQ 基于云原生重新设计的 Kafka