AtCoder AGC035E Develop (DP、图论、计数)

2024-02-15 15:32

本文主要是介绍AtCoder AGC035E Develop (DP、图论、计数),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接

https://atcoder.jp/contests/agc035/tasks/agc035_e

题解

没想出来最后一步DP宛如智障……
考虑一个数\(x\notin S\)的条件是\(x\)被删除了且在\(x\)最后一次被删除之后不能再对\(x+2\)\(x-K\)进行删除操作。也就是说\(x+2\)\(x-K\)的最晚删除时间要比\(x\)晚。那么我们从\(x\)\(x+2\)\(x-K\)连边,形成的图如果有环那么这个方案就不合法,否则合法。
如果\(K\)是偶数,显然很好算;如果\(K\)是奇数,有环的充要条件是存在一个环从某点\(a\)出发先后经过\(1\)\(+K\)边、若干条\(-2\)边、\(1\)\(+K\)边、若干条\(-2\)边,且经过的\(-2\)边的总数是\(K\). 这也就意味着我们需要让选出的点中不存在这样的一个环。
如果我们把图换一种方式看,把图排成一个每行\(2\)列的形状,让左边的奇数\(x\)和右边的偶数\(x+K\)在一行,从上往下每一层的两个(或一个)数是它上面一层对应的数\(+2\), 那么刚才提到的环就相当于若干条向上边、\(1\)条向右边、若干条向上边,向上边的总数是\(K\),最终从一个向左下的边下来。于是我们的目标就是要让“若干条向上边、\(1\)条向右边、若干条向上边”构成的最长的链长度不超过\((K+1)\).
这个可以从上往下DP: 设\(f[i][j][k]\)表示前\(i\)层,“从该层左边开始经过若干条向上边、\(1\)条向右边、若干条向上边的最长链”长度为\(j\),“从该层右边开始经过若干条向上边的最长链”长度为\(k\). 转移讨论一下两边都不选、选左、选右、左右都选即可。
时间复杂度\(O(n^3)\).

代码

#include<bits/stdc++.h>
#define llong long long
#define pii pair<int,int>
#define riterator reverse_iterator
using namespace std;inline int read()
{int x = 0,f = 1; char ch = getchar();for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}return x*f;
}const int N = 150;
llong P;
int n,m;void updsum(llong &x,llong y) {x = x+y>=P?x+y-P:x+y;}namespace Solve1
{llong f[N+3];void solve(){m>>=1; f[0] = 1ll;for(int i=1; i<=n; i++){for(int j=max(0,i-m-1); j<i; j++){updsum(f[i],f[j]);}}llong ans1 = 0ll,ans2 = 0ll;for(int i=max(0,(n>>1)-m); i<=(n>>1); i++) updsum(ans1,f[i]);for(int i=max(0,(n+1>>1)-m); i<=(n+1>>1); i++) updsum(ans2,f[i]);
//      printf("ans1=%lld ans2=%lld\n",ans1,ans2);printf("%lld\n",ans1*ans2%P);}
}namespace Solve2
{llong f[N+3][N+3][N+3];void solve(){f[0][0][0] = 1ll;for(int i=1; i+i-m<=n; i++){for(int j=0; j<=m+1; j++) for(int k=0; k<=n; k++){updsum(f[i][0][0],f[i-1][j][k]);}if(i+i<=n){for(int j=0; j<=m+1; j++) for(int k=0; k<=n; k++){updsum(f[i][0][k+1],f[i-1][j][k]);}}if(i+i-m>=1){for(int j=0; j<=m; j++) for(int k=0; k<=n; k++){updsum(f[i][j+(j>0)][0],f[i-1][j][k]);}}if(i+i<=n&&i+i-m>=1){for(int j=0; j<=m; j++) for(int k=0; k<=n; k++){int jj = max(j+1,k+2);if(jj<=m+1){updsum(f[i][jj][k+1],f[i-1][j][k]);}}}}llong ans = 0ll;for(int j=0; j<=m+1; j++) for(int k=0; k<=n; k++){updsum(ans,f[(n+m)>>1][j][k]);}printf("%lld\n",ans);}
}int main()
{scanf("%d%d%lld",&n,&m,&P);if(!(m&1)) {Solve1::solve();}else {Solve2::solve();}return 0;
}

这篇关于AtCoder AGC035E Develop (DP、图论、计数)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/711784

相关文章

hdu4826(三维DP)

这是一个百度之星的资格赛第四题 题目链接:http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意:从左上角的点到右上角的点,每个点只能走一遍,走的方向有三个:向上,向下,向右,求最大值。 咋一看像搜索题,先暴搜,TLE,然后剪枝,还是TLE.然后我就改方法,用DP来做,这题和普通dp相比,多个个向上

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

hdu4865(概率DP)

题意:已知前一天和今天的天气概率,某天的天气概率和叶子的潮湿程度的概率,n天叶子的湿度,求n天最有可能的天气情况。 思路:概率DP,dp[i][j]表示第i天天气为j的概率,状态转移如下:dp[i][j] = max(dp[i][j, dp[i-1][k]*table2[k][j]*table1[j][col] )  代码如下: #include <stdio.h>#include

usaco 1.1 Broken Necklace(DP)

直接上代码 接触的第一道dp ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于: 如果 str[i] = 'r'  ,   rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' ,  bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w',  bl[i]=b

uva 10154 DP 叠乌龟

题意: 给你几只乌龟,每只乌龟有自身的重量和力量。 每只乌龟的力量可以承受自身体重和在其上的几只乌龟的体重和内。 问最多能叠放几只乌龟。 解析: 先将乌龟按力量从小到大排列。 然后dp的时候从前往后叠,状态转移方程: dp[i][j] = dp[i - 1][j];if (dp[i - 1][j - 1] != inf && dp[i - 1][j - 1] <= t[i]

uva 10118 dP

题意: 给4列篮子,每次从某一列开始无放回拿蜡烛放入篮子里,并且篮子最多只能放5支蜡烛,数字代表蜡烛的颜色。 当拿出当前颜色的蜡烛在篮子里存在时,猪脚可以把蜡烛带回家。 问最多拿多少只蜡烛。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cs

uva 10069 DP + 大数加法

代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <queue>#include <map>#include <cl

uva 10029 HASH + DP

题意: 给一个字典,里面有好多单词。单词可以由增加、删除、变换,变成另一个单词,问能变换的最长单词长度。 解析: HASH+dp 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc

XTU 1233 n个硬币连续m个正面个数(dp)

题面: Coins Problem Description: Duoxida buys a bottle of MaiDong from a vending machine and the machine give her n coins back. She places them in a line randomly showing head face or tail face o

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。 示例 1: 输入:n = 3输出:5 示例 2: 输入:n = 1输出:1 class Solution {public int numTrees(int n) {int[] dp = new int