首页 > 其他分享 >预设性DP

预设性DP

时间:2024-08-19 17:16:23浏览次数:11  
标签:int long 预设 leq DP define dp mod

预设性DP

从最简单的起

DP搬运工2

Description

给你 n,Kn,Kn,K ,求有多少个 111 到 nnn 的排列,恰好有 KKK 个数 i(1<i<n)i(1<i<n)i(1<i<n) 满足 ai1,ai+1a_{i-1},a_{i+1}ai−1​,ai+1​ 都小于 aia_iai​ 。

Input Format

一行两个整数 n,Kn,Kn,K 。

Output Format

一行一个整数 ansansans 表示答案 mod 998244353\text{mod 998244353}mod 998244353 。

Sample

样例输入1

4 1

样例输出1

16

样例输入2

10 3

样例输出2

1841152

Hint

对于 25% 的测试点, 1n,K101\leq n,K\leq 101≤n,K≤10 ;

对于 50% 的测试点, 1n,K1001\leq n,K\leq 1001≤n,K≤100 ;

对于 100% 的测试点, 1n,K20001\leq n,K\leq 20001≤n,K≤2000 ;

保证数据有梯度

考虑\(dp_{i,j}\)表示一个长为\(i\)的序列,有\(j\)个数满足,注意一个数满足\(a_i>a_{i+1},a_{i-1}\)
我们考虑按顺序加入第\(i\)次插入\(i\),考虑不增加的情况就是在满足的旁边插入,新插入一个一定满足条件,但与他相邻原来的就不满足了,增加一个又减少一个,因为有两个相邻的所以满足的就只有\(j\)个
考虑增加一个的,就是在剩下的情况中

点击查看代码
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define lid (rt<<1)
#define rid (rt<<1|1)
// #define endl '\n'
#define pii pair<int,int>
#define ull unsigned long long
#define pb push_back
#define ts cout<<"----------------"<<endl;
#define bs bitset<65>
using namespace std;
const int N = 2005,mod=998244353;
int n,k;ll dp[N][N];
int main()
{
	speed();
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	cin>>n>>k;
	dp[1][0]=1;
	dp[2][0]=2;
	for(int i=3;i<=n;i++)
	{
		for(int j=0;j<=min(i/2,k);j++)
		{
			if(!dp[i-1][j])continue;
			dp[i][j]=(dp[i][j]+dp[i-1][j]*(1ll*(j+1)<<1ll))%mod;
			dp[i][j+1]=(dp[i][j+1]+dp[i-1][j]*(i-((j+1)<<1ll))%mod)%mod;
		}
	}
	cout<<dp[n][k]<<endl;
	return 0;
}

袋鼠

题目描述

有一个园子,里面有 nnn 个草丛排成一排,标号 1n1\sim n1∼n,有一个袋鼠,从 sss 出发,每次跳一步跳到一个其他的草丛,经过每个草丛恰好一次,最终到达 ttt。显然他会跳跃 n1n-1n−1次为了不被人类发现,袋鼠每次跳跃的方向必须与前一次不同。

具体地,如果他现在在 nownownow,他是从 prevprev prev 跳跃一次到达 nownownow 的,然后他跳跃一次到达 nextnextnext:

  • 那么如果 prev<nowprev<nowprev<now,就必须有 next<nownext<nownext<now;

  • 如果 now<prevnow<prevnow<prev,就必须有 now<nextnow<nextnow<next。

问从 sss 到 ttt 的方案数模 109+710^9+7109+7的结果。

两个路线不同,当且仅当草丛被访问的顺序不同。

保证至少有一种方案初始时可以往任意方向跳。

输入格式

一行三个整数 n,s,tn,s,tn,s,t。

输出格式

一行一个整数,代表答案。

样例 #1

样例输入 #1

4 2 3

样例输出 #1

2

数据范围与提示

对于 36% 36\% 36% 的数据,2n100 2 \leq n \leq 1002≤n≤100

对于 69% 69\% 69% 的数据,2n1000 2 \leq n \leq 10002≤n≤1000

对于 100%100\%100% 的数据,2n2×1032\le n\le 2\times 10^32≤n≤2×103,1s,tn1\le s,t\le n1≤s,t≤n

Bonus: 如果你已经 AK ,考虑 n106n \leq 10^6 n≤106 怎么做

这道题,预设性DP,不知道欧拉路能不能做,反正不会,考虑\(dp_{i,j}\),表示长度为\(i\)的多个连续段总长度,有\(j\)个不相连的连续段符合条件
还是分析:
第一种把两个连续段连起来,\(dp_{i,j}=dp_{i-1,j+1}\times j\)有\(j+1-1\)个空;
第二种,新开一个连续段(目前只有一个数)\(dp_{i,j}=dp_{i-1,j-1}\times (j-(i>t)-(i>s))\)为什么要考虑\(i\)与\(t,s\)的大小,因为\(s,t\)必须分别接在首尾,所以\(i>s,t\)时,当前有\(j\)个连续段要除去头尾\(s,t\)

点击查看代码
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define lid (rt<<1)
#define rid (rt<<1|1)
// #define endl '\n'
#define pii pair<int,int>
#define ull unsigned long long
#define pb push_back
#define ts cout<<"----------------"<<endl;
#define bs bitset<65>
using namespace std;
const int N = 2e3+5,mod=1e9+7;
int n,s,t;
ll dp[N][N];
int main()
{
	speed();
	freopen("kang.in","r",stdin);
	freopen("kang.out","w",stdout);
	cin>>n>>s>>t;//0 left
	dp[1][1]=1;
	for(int i=2;i<=n;i++)
	{
		for(ll j=1;j<=n;j++)
		{
			// if(i==1&&)
			if(i!=s&&i!=t)dp[i][j]=(dp[i][j]+dp[i-1][j+1]*j%mod+dp[i-1][j-1]*(j-(i>s)-(i>t))%mod)%mod;
			else dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%mod;
		}
	}
	cout<<dp[n][1]<<endl;
	return 0;
}

DP搬运工1

Description

给你 n,Kn,Kn,K ,求有多少个 111 到 nnn 的排列,满足相邻两个数的 maxmaxmax 的和不超过 KKK 。

Input Format

一行两个整数 n,Kn,Kn,K 。

Output Format

一行一个整数 ansansans 表示答案 mod 998244353\text{mod 998244353}mod 998244353 。

Sample

样例输入1

4 10

样例输出1

16

样例输入2

10 66

样例输出2

1983744

Hint

505050 个 测试点,第 iii 个测试点为 n=in=in=i , Kn2K\leq n^2K≤n2 。

设\(dp_{i,j,k}\)表示填到第\(i\)个数,有\(j\)个空位,和为\(k\),注意这里的空位是两个连续段相连,如\(1 3 5\)有\(2\)个空位
分两种大情况
第一种有\(0\)个空位,首尾考虑一下即可
第二种有多个空位(不考虑两端,因为无空位)

  1. 考虑放两个数中间,使两个连续段连在一块
  2. 考虑新开一个连续段
  3. 放在一个连续段的旁边
点击查看代码
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define lid (rt<<1)
#define rid (rt<<1|1)
// #define endl '\n'
#define pii pair<int,int>
#define ull unsigned long long
#define pb push_back
#define ts cout<<"----------------"<<endl;
#define bs bitset<65>
using namespace std;
const int N = 55+5,mod=998244353;
int n,K;
ll dp[N][N][N*50];
int main()
{
	speed();
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	cin>>n>>K;
	dp[1][0][0]=1;
	for(int i=2;i<=n;i++)
	{
		for(int j=0;j<=n-i+1;j++)
		{
			for(int k=0;k<=K;k++)
			{
				if(!dp[i-1][j][k])continue;
				dp[i][j+1][k]=(dp[i][j+1][k]+dp[i-1][j][k]*2%mod)%mod;
				dp[i][j][k+i]=(dp[i][j][k+i]+dp[i-1][j][k]*2%mod)%mod;
				if(j)
				{
					dp[i][j][k+i]=(dp[i][j][k+i]+dp[i-1][j][k]*j*2%mod)%mod;
					dp[i][j+1][k]=(dp[i][j+1][k]+dp[i-1][j][k]*j%mod)%mod;
					dp[i][j-1][k+2*i]=(dp[i][j-1][k+2*i]+dp[i-1][j][k]*j%mod)%mod;
				}
			}
		}
	}
	ll ans=0;
	for(int i=0;i<=K;i++)ans=(ans+dp[n][0][i])%mod;
	cout<<ans<<endl;
	return 0;
}

标签:int,long,预设,leq,DP,define,dp,mod
From: https://www.cnblogs.com/wlesq/p/18367394

相关文章

  • 【面试】阐述TCP和UDP的区别
    面试模拟场景面试官:你能阐述一下TCP和UDP的区别吗?###参考回答示例1.连接性TCP:面向连接(Connection-Oriented):TCP是一种面向连接的协议,在传输数据之前需要建立连接。在TCP通信过程中,客户端和服务器之间通过“三次握手”来建立连接,然后再进行数据传输,确保两者之间的......
  • 基于django+vue框架的实时新闻推送平台edpjq【开题报告+程序+论文】计算机毕设
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表开题报告内容研究背景在信息爆炸的时代,新闻资讯的时效性成为了媒体竞争的关键。随着互联网技术的飞速发展,人们获取新闻的方式已从传统的报纸、电视转向了手机、......
  • 树形 dp
    在树上运行的dp叫做树形dp。题单。树形dp入门问题例1.1:没有上司的舞会我们发现,对于一个节点,要么选或不选,且题目中要求求出权值最大的方案,不妨分别设\(dp_{i,0},dp_{i,1}\)为在以\(i\)为根的子树中,第\(i\)个点选或不选情况下的最大权值。那么可以得到\[dp_{i,0}=......
  • 状压 dp
    定义在动态规划中,可能存在以“集合”为状态的动态规划,应为集合不易表示,所以通常用一个二进制数来表示集合。具体的,二进制数的第\(i\)位即表示当前集合是否包含第\(i\)个元素。技巧因为许多位运算的运算优先级很迷,所以搞不明白就尽量用括号。二进制操作将\(n\)位二进......
  • @Async使用ThreadPoolTaskExecutor 多线程
    SpringBoot中的线程池ThreadPoolTaskExecutor,@Async的使用线程池@Configuration@EnableAsyncpublicclassExcutorConfig{@Bean(name="ThreadPoolTaskExecutor")publicThreadPoolTaskExecutorThreadPoolTaskExecutor(){ThreadPoolTaskExecutorex......
  • UDP的可靠性传输——KCP
    目录一:TCP是怎么做到可靠的?1、UDP和TCP的区别 2、ARQ协议(AutomaticRepeat-reQuest)2.1、ARQ协议-停等式(stop-and-wait)2.2、ARQ协议-回退n帧(go-back-n)2.3、ARQ协议-选择性重传(selectiverepeat)3、RTT和RTO4、流量控制5、如何进行流量控制(滑动窗口)6、流量控......
  • 【TCP/IP】UDP协议数据格式和报文格式
    学习一个网络协议,主要就是学习“数据格式”/“报文格式”源端口/目的端口端口号是属于传输层的概念UDP报头使用两个自己的长度来表示端口号之所以端口号的范围是0~65535,是因为底层网络协议做出了强制要求如果使用一个10w这样的端口,就会在系统底层被“截断”UDP......
  • ThreadPoolExecutor详解
    恰逢经济下行,鄙人工作、生活日趋艰难,原本美好的愿望,如今只能成为奢望。不知如何是好的我,只能精研近几年来因浮躁而荒废的知识。今天就想跟大家聊一个对我来讲看似熟悉实则陌生的工具——ThreadPoolExecutor。熟悉是因为在我负责的项目中它是一个出镜率最高演员;陌生是因为我对其......
  • 序列(dp+矩阵加速)
    第2题   序列 查看测评数据信息给定一个数集A,现在你需要构造一个长度为k的序列B,序列B的元素从数集A中任意挑选,要求B中任意相邻的两个数字的异或值二进制表示中1的个数是3的倍数,请问B的有多少种合法的构造方案?两种方案不同当且仅当存在B[i]在A中的位置不同。输入格式......
  • (nice!!!)LeetCode 552. 学生出勤记录 II(动态规划dp递归版、记忆化dfs)
    题目:552.学生出勤记录II思路:记忆化搜索dfs,细节看注释classSolution{public:constintmod=1e9+7;//状态f[u][a][b]表示:在选择第u个位置前,缺勤次数为a次,且当前连续迟到次数为b次时,可以得到的合法出勤次数intf[100010][5][5];intdfs(intu,int......