首页 > 其他分享 >插入类DP

插入类DP

时间：2024-11-08 19:29:52浏览次数：1  
标签：std ch int 插入 le pair DP define

对于这类题目的特征：

1.排列性质
2.\(100\le n \le 5\times10^3\)
3.答案和排列的上升下降的突变点有关

套路：

按照某个从小到大的顺序插入，有了这个顺序就能算贡献或者方案数
贡献往往提前计算，存在每个元素有新开一段、合并两端、连在某一段后面的不同方案
有的允许了\(A\),\(W\),\(V\),\(M\) 形状不同的最终状态可能在前面是同一状态，每个状态是为后来的状态做准备的

新开一个段和连在某个段的边上并非同一个状态，新开一个段，未来会在两端之间插入更大的数字来合并两个 段，连在一个段的边上，则未来就不会如此

关于端点：

1.如果固定了端点，往往是当 \(i\) 是左右端点时特判
2.如果没有固定左右端点，往往多加一维记录当前确定了几个端点（如果左右端点的转移/贡献相同），或者多加两维记录当前确定了左/右端点（如果左右端点的转移/贡献并不相同）

QY太强了，令我的总结旋转

按照结尾数字排名进行的插入类\(DP\)

A. 【Atcoder_DP】T-排列 (AI)

有一个长度为\(N\) 正整数排列，再给一个由 \(<\) 和 \(>\) 组成的长为 \(N - 1\) 的字符串
对于任意满足 \(1 \le i \le N - 1\)的字符 \(s_i\) ，如果 \(s_i\) 是 \(<\) 则 \(P_i < P_{i+1}\) 、 如果 \(s_i\) 是 \(>\) 则 \(P_i > P_{i+1}\) 。求满足这样性质的排列 \(P\) 的方案数
\(N\le 3000\)

考虑 \(DP\) ，设 \(f[i][j]\) 表示对于前 \(i\) 个数字，最后一个数字在前 \(i\) 个数字里排名第 \(j\) 的方案数
显然可以列出递推式

\[s[i-1]=='<' : f[i][j]=\sum^{j-1}_{k=1}{f[i-1][k]}\\ s[i-1]=='>' : f[i][j]=\sum^{i-1}_{k=j}{f[i-1][k]} \]

用前缀和优化，就可以把时间复杂度优化到\(O(n^2)\)

#include"bits/stdc++.h"

using namespace std;
constexpr int N=3015,P=1e9+7;
#define inl inline
#define regi register
#define PII pair<int,int>
#define mkp(x,y) make_pair(x,y)
//#define ll long long
//char buf_[1<<20],*_now=buf_,*_end=buf_;
//#define getchar() (_now==_end&&(_end=(_now=buf_)+fread(buf_,1,1<<20,stdin),_now==_end)?EOF:*_now++)
//namespace IO{void Unbind(){std::ios::sync_with_stdio(false);std::cin.tie(0);}}
//inl int add_(int a,int b,int p=P){return a+b>=p?a+b-p:a+b;}
//inl int sub_(int a,int b,int p=P){return a-b<0?a-b+p:a-b;}
//inl int mul_(int a,int b,int p=P){return 1ll*a*b%p;}

inl int read(void)
{
	int x=0;short f=1;char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar()) f=ch=='-'?-1:f;
	for(;ch>='0'&&ch<='9';x=(x<<3)+(x<<1)+(ch^48),ch=getchar());
	return x*f;
}

int f[N][N],sum[N][N];
int n;int ans;
char ch[N];

int main(void)
{
	n=read();
	cin>>ch+1;
	for(int i=1;i<=n;i++)	sum[1][i]=i;
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			if(ch[i-1]=='<')	f[i][j]=sum[i-1][j-1]%P;
			else	f[i][j]=(sum[i-1][i-1]-sum[i-1][j-1]+P)%P;
			sum[i][j]=(sum[i][j-1]+f[i][j])%P;
		}
	}
	printf("%d ",sum[n][n]);
	return 0;
}
B. F - Deforestation (AI)

有 \(n\) 个数：\(a_1,a_2,...,a_n\)

每次可以选择一个 \(i\) ，选择的代价是 \(a_{i-1}+a_i+a_{i+1}\)，然后令 \(a_i=0\) ，求有多少种方案，使得 \(a_1,a_2,...,a_n\) 都变为 \(0\) 的总代价最小，特别的 \(a_0=a_{n+1}=0\) \(1\le n \le 4000\)，\(1 \le a_i \le 1\times 10^9\)

考虑限制，对于 \(i\) 和 \(i+1\)

  • 先拿 \(i\) 再拿 \(i+1\) ，收益是 \(a[i]+2 \times a[i+1]\)
  • 先拿 \(i+1\) 再拿 \(i\) ， 收益是 \(a[i+1]+2 \times a[i]\)

显然，对于更大的那个，先拿是最优的，如果相等就随意， \(a_i\) 是原数组， \(pos_i\) 是 \(i\) 号是第几个取

于是类似于 \(T1\)

\[a[i-1]>a[i]\space:\space f[i][j]=\sum_{k=1}^{j-1}{f[i-1][k]}\\ a[i-1]<a[i]\space:\space f[i][j]=\sum_{k=j}^{i-1}{f[i-1][k]}\\ a[i-1]=a[i]\space:\space f[i][j]=\sum_{k=1}^{i-1}{f[i-1][k]} \]

#include"bits/stdc++.h"

using namespace std;
constexpr int N=5015,P=1e9+7;
#define inl inline
#define regi register
#define PII pair<int,int>
#define mkp(x,y) make_pair(x,y)
//#define ll long long
//char buf_[1<<20],*_now=buf_,*_end=buf_;
//#define getchar() (_now==_end&&(_end=(_now=buf_)+fread(buf_,1,1<<20,stdin),_now==_end)?EOF:*_now++)
//namespace IO{void Unbind(){std::ios::sync_with_stdio(false);std::cin.tie(0);}}
//inl int add_(int a,int b,int p=P){return a+b>=p?a+b-p:a+b;}
//inl int sub_(int a,int b,int p=P){return a-b<0?a-b+p:a-b;}
//inl int mul_(int a,int b,int p=P){return 1ll*a*b%p;}

inl int read(void)
{
	int x=0;short f=1;char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar()) f=ch=='-'?-1:f;
	for(;ch>='0'&&ch<='9';x=(x<<3)+(x<<1)+(ch^48),ch=getchar());
	return x*f;
}

int f[N][N],sum[N][N];
int n,a[N];

int main(void)
{
	n = read();
	for (int i = 1;i <= n;i ++)	a[i] = read();
	f[1][1] = 1;
	for (int i = 1;i <= n;i ++)	sum[1][i] = 1;
	for (int i = 2; i <= n;i ++)
	{
		for (int j = 1;j <= i;j ++)
		{
			if (a[i] < a[i - 1])	f[i][j] = sum[i - 1][j - 1];	else
			if (a[i] > a[i - 1])	f[i][j] = (sum[i - 1][i - 1] - sum[i - 1][j - 1] + P) % P;	else
			if (a[i] == a[i - 1])	f[i][j] = sum[i - 1][i - 1];
			sum[i][j] = (sum[i][j - 1] + f[i][j]) % P;
		}
	}
	printf ("%d ",sum[n][n]);
	return 0;
}
C. kangaroo

袋鼠，有 \(n\) 个草丛排成一排，编号从 \(1\) 到 \(n\) ，有一个袋鼠，从 \(s\) 出发，每次挑一步到一个其他的草丛，经过每个草丛恰好一次，最终到达 \(t\) ，显然他会跳跃 \(n-1\) 次，未来不被人类发现，袋鼠每次跳跃的方向必须与前一次不同
问从 \(s\) 到 \(t\) 的方案数 \(\mod 10^9+7\)的结果
两个路线不同，当且仅当草丛被访问的顺序不同，保证至少有一种方案初始时可以往任意方向跳
\(2\le n \le 2\times 10^3\)，\(1 \le s,t \le n\)

用 \(f[i][j]\) 表示前 \(i\) 个数字，分成了 \(j\) 段，规定每段都是 一个元素 或者 低高低 或者 地高低高低 \(...\)
对于处理 \(f[i][j]\) 时，第 \(i\) 个数字对于前 \(i-1\) 个数字都是高的，所以他可以用来合并两个段，或者新开一段

\(f[i][j]=f[i-1][j+1]\times j+f[i-1][j-1]\times j\)

考虑需要处理 \(s,t\) 的关系

\[i=s \|\| i=t \space : \space f[i][j]=f[i-1][j-1]+f[i-1][j]\\ i≠s \&\& i≠t \space : \space f[i][j]=f[i-1][j+1]\times j+f[i-1][j-1]\times(j-(i>s)-(i>t)) \]

\(answer = f[n][1]\)

#include"bits/stdc++.h"

using namespace std;
constexpr int N=2e3+15,P=1e9+7;
#define inl inline
#define regi register
#define PII pair<int,int>
#define mkp(x,y) make_pair(x,y)
#define ll long long
//char buf_[1<<20],*_now=buf_,*_end=buf_;
//#define getchar() (_now==_end&&(_end=(_now=buf_)+fread(buf_,1,1<<20,stdin),_now==_end)?EOF:*_now++)
//namespace IO{void Unbind(){std::ios::sync_with_stdio(false);std::cin.tie(0);}}
//inl int add_(int a,int b,int p=P){return a+b>=p?a+b-p:a+b;}
//inl int sub_(int a,int b,int p=P){return a-b<0?a-b+p:a-b;}
//inl int mul_(int a,int b,int p=P){return 1ll*a*b%p;}

inl int read(void)
{
	int x=0;short f=1;char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar()) f=ch=='-'?-1:f;
	for(;ch>='0'&&ch<='9';x=(x<<3)+(x<<1)+(ch^48),ch=getchar());
	return x*f;
}

int n,s,t;
ll f[N][N];

int main(void)
{
	n = read(),s = read(),t = read();
	f[1][1] = 1;
	for(int i = 2;i <= n;i ++)
	{
		for(int j = 1;j <= i;j ++)
		{
			if(i != s && i != t)	f[i][j] = (j * f[i - 1][j + 1] % P + 
				(j - (i > s) - (i > t)) * f[i - 1][j - 1] % P) % P;
			else	f[i][j] = f[i - 1][j - 1] + f[i - 1][j];
		}
	}
	printf("%lld ",f[n][1]);
	return 0;
}
D.CF704B Ant Man

有 \(n\) 个元素，第 \(i\) 个元素有五个参数 \(x_i,a_i,b_i,c_i,d_i\) ，需要求出一个从 \(1\) 到 \(n\) 的排列 \(p\) ，满足 \(p_1=s,p_n=e\) ，同时最小化这个排列的权值，定义一个排列的权值为 \(\sum_{i=1}^{n-1}{f(p_i.p_{i+1})}\) ， 其中 \(f(i,j)\) 的值有两种情况：

  • 若 \(i>j\) ， 则 \(f(i,j) = x_i - x_j+c_i+b_j\)
  • 若 \(i<j\) ， 则 \(f(i,j) = x_j - x_i + d_i + a_j\)

\(n\le 5\times 10^3,s≠e,1\le x_1 < x_2 < ... < x_n \le 10^9,1\le a_i,b_i,c_i,d_i \le 10^9\)

用 \(f[i][j]\) 表示前 \(i\) 个数字，有 \(j\) 段的最小花费

\(f[0][1]=0\)

普通的情况
\(f[i][j]=f[i-1][j-1]-x[i]\times 2+b[i]+d[i]\) 作为新开一段，这一段必然是在未来作为高低高的低出现的，所以他对答案的贡献是 \(-2\times x[i]+b[i]+d[i]\)

\(f[i][j]=f[i-1][j+1]+x[i]\times 2+a[i]+c[i]\) 合并两个段，这个点最为低高低的高出现，对答案的贡献是\(2\times x[i]+c[i]+a[i]\)

\(f[i][j]=f[i-1][j]+b[i]+c[i]\) 往某个段前面放，作为高中低的中出现，对答案的贡献是 \(b[i]+c[i]\)

\(f[i][j]=f[i-1][j]+a[i]+d[i]\) 往某个段后面放，作为低中高的中出现，对答案的贡献是 \(a[i]+d[i]\)

对于起点 \(s\) ， \(f[i][j]=f[i-1][j]+x[i]+c[i]\) 连接在某个段前面，于是排列高低起手，\(s\) 的贡献是 \(x[i]+c[i]\)
新开一个段，\(f[i][j]=f[i-1][j-1]-x[i]+d[i]\)，于是最终排列低高起手， \(s\) 的贡献是 \(-x[i]+d[i]\)

对于终点 \(t\)，\(f[i][j]=f[i-1][j]+x[i]+a[i]\) ，于是最终排列低高结尾，\(t\) 的贡献是\(x[i]+a[i]\)
新开一个段， \(f[i][j]=f[i-1][j-1]-x[i]+b[i]\)， 于是最终排列高低结尾， \(t\) 的贡献是 \(-x[i]+b[i]\)

考虑起点和终点固定下来，对转移有什么影响\(:\)
想要新开一段时，当 \(i>s\&\&i>t\) 时，此时 \(s,t\) 做起点终点，只有一段时不能新开一段
想往某个段的前面放，要么 \(s\) 没出现，要么 \(s\) 出现了并且段数大于 \(1\) 才能往前放
想往某个段的后面放，要么 \(t\) 没出现，要么 \(t\) 出现了，并且段数大于 \(1\) 才能往后放

\(answer=f[n][1]\)

#include"bits/stdc++.h"

using namespace std;
constexpr int N=5e3+15;
#define inl inline
#define regi register
#define PII pair<int,int>
#define mkp(x,y) make_pair(x,y)
#define ll long long
//char buf_[1<<20],*_now=buf_,*_end=buf_;
//#define getchar() (_now==_end&&(_end=(_now=buf_)+fread(buf_,1,1<<20,stdin),_now==_end)?EOF:*_now++)
//namespace IO{void Unbind(){std::ios::sync_with_stdio(false);std::cin.tie(0);}}
//inl int add_(int a,int b,int p=P){return a+b>=p?a+b-p:a+b;}
//inl int sub_(int a,int b,int p=P){return a-b<0?a-b+p:a-b;}
//inl int mul_(int a,int b,int p=P){return 1ll*a*b%p;}

inl int read(void)
{
	int x=0;short f=1;char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar()) f=ch=='-'?-1:f;
	for(;ch>='0'&&ch<='9';x=(x<<3)+(x<<1)+(ch^48),ch=getchar());
	return x*f;
}

ll f[N][N];
int n,s,e;int x[N],a[N],b[N],c[N],d[N];

inl void cmin(ll &a,ll b){return a=min(a,b),void();} 

int main(void)
{
	n=read(),s=read(),e=read();
	for(int i=1;i<=n;i++)	x[i]=read();for(int i=1;i<=n;i++)	a[i]=read();for(int i=1;i<=n;i++)	b[i]=read();for(int i=1;i<=n;i++)	c[i]=read();for(int i=1;i<=n;i++)	d[i]=read();
	memset(f,0x3f,sizeof f);
	f[0][0]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			if(i==e)	cmin(f[i][j],min(f[i-1][j]+x[i]+a[i],f[i-1][j-1]-x[i]+b[i]));	else
			if(i==s)	cmin(f[i][j],min(f[i-1][j-1]-x[i]+d[i],f[i-1][j]+x[i]+c[i]));	else
			{
				if(j>(i>s)+(i>e))	cmin(f[i][j],f[i-1][j-1]-2*x[i]+b[i]+d[i]);
				if(j>1||i<s)	cmin(f[i][j],f[i-1][j]+b[i]+c[i]);
				if(j>1||i<e)	cmin(f[i][j],f[i-1][j]+a[i]+d[i]);
				cmin(f[i][j],f[i-1][j+1]+2*x[i]+a[i]+c[i]);
			}
		}
	}
	printf("%lld ",f[n][1]);
	return 0;
}
E. 「JOI Open 2016」摩天大楼

有 \(N\) 个整数， \(a_1,a_2,a_3,...,a_N\)，按照一定顺序排序，假设排列为 \(f_1,f_2,...,f_N\) ，要求： \(\|f_1-f_2\|+\|f_2-f_3\|+...\|f_{N-1}-f_N\|\le L\) ，求满足题意的排列的方案数 \((\mod 10^9+7)\)

为了规避掉绝对值，先排个序。

这题没有规定左右端点，考虑\(dp\)的时候加一维

\(f[i][j][sum][d]\)表示前 \(i\) 大的 \(a\)，有 \(j\) 段，当前已经固定了 \(d\) 个端点（左右端点），和为 \(sum\)

把 \(a_i\) 插入的贡献看成是把之前的 \(j\) 段的每一段的左右端点都变为 \(a_i\) ，需要花费 \((2 \times j-d)\cdot\|f[a]-a[i-1]\|\)，然后插入 \(a_i\) 时无需贡献，所以 \(a_i-a_{i-1}\)的贡献是和插入前的段数和端点数量相关的，有 \(j\) 段，\(d\) 个端点时，贡献为 \((a_i-a_{i-1})\cdot(2\times j-d)\)

考虑转移

\[设\space p \space 为\space 当前贡献，t \space 为所枚举到的\space f[i][j][k][d] \\ 新开一个：f[i+1][j+1][p][d]=f[i+1][j+1][p][d]+t*(j+1-d)\\ 放在某一段的左右（j\le 1）：f[i+1][j][p][d]=f[i+1][j][p][d]+t*(2*j-d)\\ 合并两个（j\le 2）：f[i+1][j-1][p][d]=f[i+1][j-1][p][d]+t*(j-1)\\ 让a_i新开一段（d < 2）：f[i+1][j+1][p][d+1]=f[i+1][j+1][p][d+1]+t*(2-d)\\ 让a_i做端点（d < 2 \&\& j ≥ 1）：f[i+1][j][p][d+1]=f[i+1][j][p][d+1]+t*(2-d)\\ \]

#include"bits/stdc++.h"

using namespace std;
constexpr int N=115,L=1015,P=1e9+7;
#define inl inline
#define regi register
#define PII pair<int,int>
#define mkp(x,y) make_pair(x,y)
#define ll long long
//char buf_[1<<20],*_now=buf_,*_end=buf_;
//#define getchar() (_now==_end&&(_end=(_now=buf_)+fread(buf_,1,1<<20,stdin),_now==_end)?EOF:*_now++)
//namespace IO{void Unbind(){std::ios::sync_with_stdio(false);std::cin.tie(0);}}
inl void add_(ll &a,ll b,int p=P){return a=(a+b>=p?a+b-p:a+b),void();}
//inl int sub_(int a,int b,int p=P){return a-b<0?a-b+p:a-b;}
//inl int mul_(int a,int b,int p=P){return 1ll*a*b%p;}

inl int read(void)
{
	int x=0;short f=1;char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar()) f=ch=='-'?-1:f;
	for(;ch>='0'&&ch<='9';x=(x<<3)+(x<<1)+(ch^48),ch=getchar());
	return x*f;
}

ll f[N][N][L][3];int a[N],n,l;

int main(void)
{
	n=read(),l=read();
	for(int i=1;i<=n;i++)	a[i]=read();
	sort(a+1,a+1+n);
	f[0][0][0][0]=1;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<=i;j++)
		{
			for(int k=0;k<=l;k++)
			{
				for(short d=0;d<3;d++)
				{
					ll p=k+(a[i+1]-a[i])*(2*j-d),t=f[i][j][k][d];
					if(!t||p>l)	continue;add_(f[i+1][j+1][p][d],t*(j+1-d)%P);
					if(j>=2)	add_(f[i+1][j-1][p][d],t*(j-1)%P);
					if(j>=1)	add_(f[i+1][j][p][d],t*(2*j-d)%P);
					if(d<2)
					{
						add_(f[i+1][j+1][p][d+1],t*(2-d));
						if(j>=1)	add_(f[i+1][j][p][d+1],t*(2-d)%P);
					}
				}
			}
		}
	}
	ll ans=0;
	for(int i=0;i<=l;i++)	add_(ans,f[n][1][i][2]);
	printf("%lld",n==1?1:ans);
	return 0;
}
P2612 [ZJOI2012] 波浪

随机生成一个排列

排列的价值定义为相邻两个数差的绝对值累加

问价值大于等于 \(M\) 的概率

\(L = \| a_2-a_1 \|+\|a_3-a_2\|...\)

与上题类似，现在有 \(n\) 个空位，从小到大以此放入 $1 $ ~ $ n$ 个数

设计 \(f[l][i][j][k]\) 为放了 \(i\) 个数,形成 \(j\) 个连通块,价值为 \(k\) 且有 $l $ 个边界放了数的方案

转移类似上一题，注意得开 \(\_\_float 128\)，代码用了两种 ， 小测试点快一些

#include"bits/stdc++.h"

using namespace std;
constexpr int N=5015;
#define inl inline
#define regi register
#define PII pair<int,int>
#define mkp(x,y) make_pair(x,y)
#define ld __float128
//#define ll long long
//char buf_[1<<20],*_now=buf_,*_end=buf_;
//#define getchar() (_now==_end&&(_end=(_now=buf_)+fread(buf_,1,1<<20,stdin),_now==_end)?EOF:*_now++)
//namespace IO{void Unbind(){std::ios::sync_with_stdio(false);std::cin.tie(0);}}
//inl int add_(int a,int b,int p=P){return a+b>=p?a+b-p:a+b;}
//inl int sub_(int a,int b,int p=P){return a-b<0?a-b+p:a-b;}
//inl int mul_(int a,int b,int p=P){return 1ll*a*b%p;}

inl int read(void)
{
	int x=0;short f=1;char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar()) f=ch=='-'?-1:f;
	for(;ch>='0'&&ch<='9';x=(x<<3)+(x<<1)+(ch^48),ch=getchar());
	return x*f;
}
int n,m,K;
template <class T>
void Print(T ans)
{
	int num[100];
	num[0]=0;
	ans=ans*10;
	for(int i=1;i<K;i++)
	{
		num[i]=(int)ans;
		ans=(ans-num[i])*10;
	}
	num[K]=(int)(ans+0.5);
	for(int i=K;i>=1;i--)	if(num[i]>=10)	num[i]-=10,num[i-1]++;
	printf("%d.",num[0]);
	for(int i=1;i<=K;i++)	printf("%d",num[i]);
	puts("");
}
int l;
ld ans;
template <class T>
void solve(T f[][115][3][N])
{
	f[0][0][0][0]=1;
	for(int i=0;i<n;i++)
	{
		int cur=i%2;
		for(int j=0;j<=i+1;j++)	for(int op=0;op<=2;op++)	for(int s=0;s<=(n*n)/2;s++)	f[!cur][j][op][s]=0;
		for(int j=(i!=0);j<=i;j++)	for(int op=0;op<=2;op++)	for(int s=0,ts=2*j-op;ts<=(n*n)/2;s++,ts++)
		{
			if(!f[cur][j][op][s])	continue;
			ld t=f[cur][j][op][s];
			f[!cur][j+1][op][ts]=f[!cur][j+1][op][ts]+t*(j+1-op);
			f[!cur][j][op][ts]+=t*(2*j-op);
			if(j)	f[!cur][j-1][op][ts]+=t*(j-1);
			if(op!=2)
				f[!cur][j+1][op+1][ts]+=t*(2-op),f[!cur][j][op+1][ts]+=t*(2-op);
		}
	}
	for(int i=l;i<=5000;i++)	ans=(ans+f[n%2][1][2][i]);
	for(int i=1;i<=n;i++)	ans=ans/i;
	Print(ans);
}
ld f1[2][115][3][N];
double f2[2][115][3][N];
int main(void)
{
	n=read(),l=read(),K=read();
	if(n==1)	Print(1),exit(0);
	if(n<=8)	solve(f2);else	solve(f1);
	return 0;
}
CF1515E Phoenix and Computers

给定 \(N\) 台电脑，起初每台电脑都是关闭的
现在你可以随意打开电脑，但如果第 \(i−1\)、第 \(i+1\) 台电脑是开启的，则第 \(i\) 台电脑也会自动开启，而你无法手动开启它
问你有多少种打开电脑的方法，使得最后所有电脑都是开着的

\(f[i][j]\)表示有\(i\)个电脑，组成\(j\)个连续已开启的段

转移有 新建段，段扩增，段合并 共五种情况

#include"bits/stdc++.h"

using namespace std;
constexpr int N=415;
#define inl inline
#define regi register
#define PII pair<int,int>
#define mkp(x,y) make_pair(x,y)
#define ll long long

//char buf_[1<<20],*_now=buf_,*_end=buf_;
//#define getchar() (_now==_end&&(_end=(_now=buf_)+fread(buf_,1,1<<20,stdin),_now==_end)?EOF:*_now++)
//namespace IO{void Unbind(){std::ios::sync_with_stdio(false);std::cin.tie(0);}}
//inl void add_(ll &a,ll b,int p=P){return a=(a+b>=p?a+b-p:a+b),void();}
//inl int sub_(int a,int b,int p=P){return a-b<0?a-b+p:a-b;}
//inl int mul_(int a,int b,int p=P){return 1ll*a*b%p;}

inl int read(void)
{
	int x=0;short f=1;char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar()) f=ch=='-'?-1:f;
	for(;ch>='0'&&ch<='9';x=(x<<3)+(x<<1)+(ch^48),ch=getchar());
	return x*f;
}

int n,P;
ll f[N][N];

int main(void)
{
	n=read(),P=read(),f[0][0]=1;
	for(int i=1;i<=n;i++)	for(int j=1;j<=i;j++)
	{
		f[i][j]+=f[i-1][j]*2*j;
		if(i>=2)	f[i][j]+=f[i-2][j]*2*j,f[i][j]+=f[i-2][j+1]*2*j;
		if(i>=3)	f[i][j]+=f[i-3][j+1]*j;
		(f[i][j]+=f[i-1][j-1]*j)%=P;
	}
	printf("%lld",f[n][1]);
	return 0;
}
P7967 [COCI2021-2022#2] Magneti

给定 \(n\) 个磁铁和 \(l\) 个空位，其中相邻空位之间的距离为 \(1\)，每个空位可放置一个磁铁。所有 \(n\) 个磁铁都必须被放置。每个磁铁可以吸引距离小于 \(r_i\) 的其它磁铁。

求所有磁铁互不吸引的方案总数对 \(10^9+7\) 取模的结果。

\(f[i][j][s]\)，表示用了前\(i\)个，\(j\)段，段的长度之和为\(s\) 方案数

\[放在某一段的边上：(s>=r[i])f[i][j][s]+=f[i-1][j][s-r[i]]*j*2\\ 新开一段(s>=1)：f[i][j][s]+=f[i-1][j-1][s-1]*j\\ 合并两段(s>=2*r[i]-1)：f[i][j][s]+=f[i-1][j+1][s 2*r[i]+1]*j \]

最后还需要组合数一下。对于\(f[n][1][i]\)，需要给\(n\)个磁铁的前后中间共\(n+1\)个“盒子”放置\(l-i\)空格，可以为空

转化为\(n+1\)个盒子，\(l-i+n+1\)个空格，不可以为空，抓化成\(l-i+n\)个间隙，赛\(n\)个挡板

\(ans=\sum{f[n][1][i]}*C(n+l-i,n)\)

#include"bits/stdc++.h"

using namespace std;
constexpr int N=2e5+15,P=1e9+7;
#define inl inline
#define regi register int
#define PII pair<int,int>
#define mkp(x,y) make_pair(x,y)
#define ll long long
//char buf_[1<<20],*_now=buf_,*_end=buf_;
//#define getchar() (_now==_end&&(_end=(_now=buf_)+fread(buf_,1,1<<20,stdin),_now==_end)?EOF:*_now++)
//namespace IO{void Unbind(){std::ios::sync_with_stdio(false);std::cin.tie(0);}}
//inl int add_(int a,int b,int p=P){return a+b>=p?a+b-p:a+b;}
//inl int sub_(int a,int b,int p=P){return a-b<0?a-b+p:a-b;}
//inl int mul_(int a,int b,int p=P){return 1ll*a*b%p;}

inl int read(void)
{
	int x=0;short f=1;char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar()) f=ch=='-'?-1:f;
	for(;ch>='0'&&ch<='9';x=(x<<3)+(x<<1)+(ch^48),ch=getchar());
	return x*f;
}

ll fac[N],inv[N];
ll qpow(ll a,ll b){ll res=1;a%=P;while(b){if(b&1)res=res*a%P;a=a*a%P;b>>=1;}return res;}
void init(int n_)
{
	fac[0]=inv[0]=1;
	for(regi i=1;i<=n_;i++)	fac[i]=fac[i-1]*i%P;
	inv[n_]=qpow(fac[n_],P-2);
	for(regi i=n_-1;i>=1;i--)	inv[i]=inv[i+1]*(i+1)%P;
}
ll C(ll n,ll m){return fac[n]*inv[n-m]%P*inv[m]%P;}
ll n,l,r[N],ans;
ll f[65][65][10015];
int main(void)
{
//	freopen("magnet.in","r",stdin),freopen("magnet.out","w",stdout);
	n=read(),l=read();
	init(20000);
	for(int i=1;i<=n;i++)	r[i]=read();
	sort(r+1,r+1+n);
	f[0][0][0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			for(int s=0;s<=l;s++)
			{
				if(s>=r[i])	(f[i][j][s]+=f[i-1][j][s-r[i]]*j*2)%=P;
				if(s>=1)	(f[i][j][s]+=f[i-1][j-1][s-1]*j)%=P;
				if(s>=2*r[i]-1)	(f[i][j][s]+=f[i-1][j+1][s-2*r[i]+1]*j)%=P;
			}
		}
	}
	for(int i=0;i<=l;i++)	ans=(ans+(f[n][1][i]*C(l+n-i,n))%P)%P;
	printf("%lld",ans);
	return 0;
}

再附上我们强大的\(QY\)学长的[\(cf\)账号](zzuqy - Codeforces)

标签：std,ch,int,插入,le,pair,DP,define
From： https://www.cnblogs.com/empty-space/p/18535786

相关文章

  • 大模型--训练 加速之 数据并行(DP, DDP与ZeRO)-上-12
    目录1.参考2.总结3.分布式数据并行(DDP)4.总结1.参考https://zhuanlan.zhihu.com/p/6171339712.总结以GoogleGPipe为代表的流水线并行范式，当模型太大，一块GPU放不下时，流水线并行，将模型的不同层放到不同的GPU上，通过切割mini-batch实现对训练数据的流水线处理，提升GPU计算......
  • 代码随想录算法训练营第二十天|leetcode235. 二叉搜索树的最近公共祖先、leetcode701.
    1leetcode235.二叉搜索树的最近公共祖先题目链接：235.二叉搜索树的最近公共祖先-力扣（LeetCode）文章链接：代码随想录视频链接：二叉搜索树找祖先就有点不一样了！|235.二叉搜索树的最近公共祖先_哔哩哔哩_bilibili思路：用之前一样的方法，哈哈哈哈哈，好处就是做出来了，但是我觉得需......
  • 数据结构学习笔记---线性表：顺序表（插入）
    顺序表的基本操作——插入首先，静态分配一个顺序表#include<stdio.h>#include<stdlib.h>#defineMaxSize5//定义队列的最大长度typedefstruct{ intdata[MaxSize]; intlength;}SqList;然后实现插入方法，for循环我们提前插入了四个元素，顺序排放原理是以i为......
  • 知识分享：Air780E软件之UDP应用示例
    一、UDP概述UDP（用户数据报协议，UserDatagramProtocol）是一种无连接的、不可靠的传输层协议，主要用于实现网络中的快速通讯。以下是UDP通讯的主要特点：1.1无连接通讯：UDP在发送数据之前不需要建立连接，这大大减少了通讯的延迟。发送方只需将数据包封装成UDP报文，并附上目的地址......
  • 数据结构_链表_双向循环链表 & 栈 的初始化、插入、删除、修改、查询打印（基于C语言实
    一、双向循环链表的原理与应用双向循环链表与双向链表的区别：指的是双向循环链表的首结点中的prev指针成员指向链表的尾结点，并且双向循环链表的尾结点里的next指针成员指向链表的首结点，所以双向循环链表也属于环形结构。由于带头结点更加方便用户进行数据访问，所以本次创建一条带......
  • 数据结构_链表_单向循环链表 & 双向链表的初始化、插入、删除、修改、查询打印（基于C语
    一、单向循环链表的原理与应用思考：对于单向链表而言，想要遍历链表，则必须从链表的首结点开始进行遍历，请问有没有更简单的方案实现链表中的数据的增删改查？回答：是有的，可以使用单向循环的链表进行设计，单向循环的链表的使用规则和普通的单向链表没有较大的区别，需要注意：单向循环链表的......
  • 洛谷 P2113 看球泡妹子（DP）
    传送门https://www.luogu.com.cn/problem/P2113解题思路可以设  表示前  场比赛看了  场，小红的满足度为  的最大精彩度。然后可以枚举前面的一个比赛 ，可以得到转移方程：但是，我们发现数组空间有一点小大，可以优化一下。发现每一次转移都是 ，于是可以滚动数组优化空......
  • 插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序
    #include<stdio.h>#include<stdlib.h>//插入排序voidInsertSort(intA[],intn){inti,j,temp;for(i=1;i<n;i++){temp=A[i];j=i-1;while(j>=0&&A[j]>temp){A......
  • 链表的插入排序
    #include<stdio.h>#include<stdlib.h>//定义链表节点结构typedefstructNode{intdata;structNode*next;}Node;//创建新节点Node*createNode(intdata){Node*newNode=(Node*)malloc(sizeof(Node));newNode->data=data;newN......
  • P10161 [DTCPC 2024] 小方的疑惑 10 [构造 + 背包DP]
    P10161[DTCPC2024]小方的疑惑10Solution一开始看这题的时候，我们可能会觉得无从下手，这时不妨列出几种方案，计算它们的贡献，尝试得到一些启发。画来画去，发现无非就是并列和包含两种情况，并列就是()()()()，设它一共由\(x\)对括号组成，那么它的总贡献是\(x\times(x+1)\div......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99