首页 > 其他分享 >计数dp

计数dp

时间：2023-04-29 22:55:23浏览次数：47  
标签：int void args rd 计数 wt inline dp

CODE FESTIVAL 2016 Final

\(n,m\) 很小，可以设很暴力的状态

发现我每次就是一条路径然后回到 \(1\) 所在的强连通分量，不关心我现在在哪个点，所以设 \(f_{i,j,k}\) 表示现在走了 \(i\) 步， \(1\) 所在的强连通分量里面有 \(j\) 个点，现在走了 \(k\) 个点还没有回到强连通分量里面

转移也非常简单

\(f_{i+1,j,k+1}=f_{i,j,k} \times (n-j-k)\) 这条路径继续走不会到强连通分量

\(f_{i+1,j,k}=f_{i,j,k} \times k\) 这条路径继续走，但是走到了之前这条路径经过的点

\(f_{i+1,j+k,0}=f_{i,j,k} \times j\) 走回强连通分量

然后就没了.

\(code\)

#include<cstdio>
#include<iostream>
namespace IO{
	template<typename T> inline void rd(T &x){
		x=0;bool f=0;char c=0;
		while(c<'0'||c>'9') f|=c=='-',c=getchar();
		while('0'<=c&&c<='9') x=x*10+(c^48),c=getchar();
		x=f?-x:x;
	}
	template<typename T,typename ...Args> inline void rd(T &x,Args &...args){rd(x),rd(args...);}
	template<typename T> inline void wt(char c,T x){
		int stk[114],top=0;
		if(x<0) x=-x,putchar('-');
		do stk[++top]=x%10,x/=10; while(x);
		while(top) putchar(stk[top--]+'0');
		putchar(c);
	}
	template<typename T,typename ...Args> inline void wt(char c,T &x,Args &...args){wt(c,x),wt(c,args...);}
};
using namespace IO;
using namespace std;
const int P=1e9+7;
const int N=307;
int f[N][N][N];
int n,m;
int main(){
	#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
	#endif
	rd(n,m);
	f[0][1][0]=1;
	for(int i=0;i<=m;i++){
		for(int j=1;j<=n;j++){
			for(int k=0;k<=n;k++){
				f[i+1][j][k+1]=(f[i+1][j][k+1]+1ll*f[i][j][k]*(n-j-k))%P;
				f[i+1][j][k]=(f[i+1][j][k]+1ll*f[i][j][k]*k)%P;
				f[i+1][j+k][0]=(f[i+1][j+k][0]+1ll*f[i][j][k]*j)%P;
			}
		}
	}
	int res=0;
	for(int i=0;i<=n;i++) res=(res+f[m][n][i])%P;
	wt('\n',res);
	return 0;
}

Aizu 2439 Hakone

这是什么OJ/yiw

神仙题，根本想不到/kk

首先发现等于鸟用没有，直接去掉

看完题解之后我们知道可以建二分图，第 \(i\) 个左部点向右部所有满足限制的点连边，现在就把问题转化成了二分图最大匹配数计数了

但是这是 \(NP\) 的……

发现我们图建的非常好看，对于 \(i\) 连的一定是点集 \([1,i]\) 或 \([i,n]\)

有了这个东西好像就是能做的了

设 \(f_{i,j,k}\) 表示同时考虑二分图两边的第 \(i\) 个点，前面有 \(j\) 个左部点没有匹配上， \(k\) 个左部点没有匹配上

转移

\(f_{i,j,k}=f_{i-1,j,k} \times k\) 当是小于号时

\(f_{i,j,k}=f_{i-1,j,k} \times j\) 当是大于号时

\(f_{i,j,k}=f_{i-1,j+1,k+1} \times k \times j\) 都可以转移

现在的复杂度是 \(O(n^3)\) 的，已经可以通过本题

但是我们惊奇的发现，这个 \(dp\) 的转移的时候 \(j,k\) 加减的数值是一样的，也就是说，\(dp\) 中的合法状态都满足 \(j=k\) 所以我们可以直接去掉一维，这样时间复杂度就是 \(O(n^2)\) 的了

\(code\)

#include<cstdio>
#include<iostream>
namespace IO{
	template<typename T> inline void rd(T &x){
		x=0;bool f=0;char c=0;
		while(c<'0'||c>'9') f|=c=='-',c=getchar();
		while('0'<=c&&c<='9') x=x*10+(c^48),c=getchar();
		x=f?-x:x;
	}
	template<typename T,typename ...Args> inline void rd(T &x,Args &...args){rd(x),rd(args...);}
	template<typename T> inline void wt(char c,T x){
		int stk[114],top=0;
		if(x<0) x=-x,putchar('-');
		do stk[++top]=x%10,x/=10; while(x);
		while(top) putchar(stk[top--]+'0');
		putchar(c);
	}
	template<typename T,typename ...Args> inline void wt(char c,T &x,Args &...args){wt(c,x),wt(c,args...);}
};
using namespace IO;
using namespace std;
const int P=1e9+7;
const int N=207;
int f[N][N];
int n,m;
int opt[N];
int main(){
	#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
	#endif
	rd(n);
	for(int i=1;i<=n;i++){
		char s=getchar();
		while(s!='U'&&s!='D'&&s!='-') s=getchar();
		if(s!='-') opt[++m]=s=='U';
	}
	n=m;
	f[0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=n;j++){
			if(opt[i]) f[i][j]=((j-1>=0?f[i-1][j-1]:0)+1ll*f[i-1][j]*j)%P;
			else f[i][j]=(1ll*f[i-1][j]*j%P+1ll*f[i-1][j+1]*(j+1)%P*(j+1)%P)%P;
		}
	}
	wt('\n',f[n][0]);
	return 0;
}

我是真的菜，这个题做了一晚上/kk

注意要输出行末换行

Aizu 2333 My friends are small

我的朋友很小/yiw，日文翻译是我的朋友很少

傻逼题

将 \(W\) 从大到小排序，最后一个没选的就是最小的

数据范围很小，直接记进状态里面就好了

记得滚动数组

\(code\)

#include<cstdio>
#include<iostream>
#include<algorithm>
namespace IO{
	template<typename T> inline void rd(T &x){
		x=0;bool f=0;char c=0;
		while(c<'0'||c>'9') f|=c=='-',c=getchar();
		while('0'<=c&&c<='9') x=x*10+(c^48),c=getchar();
		x=f?-x:x;
	}
	template<typename T,typename ...Args> inline void rd(T &x,Args &...args){rd(x),rd(args...);}
	template<typename T> inline void wt(char c,T x){
		int stk[114],top=0;
		if(x<0) x=-x,putchar('-');
		do stk[++top]=x%10,x/=10; while(x);
		while(top) putchar(stk[top--]+'0');
		putchar(c);
	}
	template<typename T,typename ...Args> inline void wt(char c,T &x,Args &...args){wt(c,x),wt(c,args...);}
};
using namespace IO;
using namespace std;
const int INF = 1e9;
const int P = 1e9 + 7;
const int N=207,M=1e4+7;
int f[2][M][N];
int n,m;
int w[N];
inline int cmp(int x,int y){return x>y;}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
	#endif
	rd(n,m);
	for(int i=1;i<=n;i++) rd(w[i]);
	sort(w+1,w+1+n,cmp);
	w[0]=INF;
	f[0][0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m;j++){
			for(int k=0;k<=i;k++)f[i&1][j][k]=0;
		}
		for(int j=0;j<=m;j++){
			for(int k=0;k<=i;k++){
				if(j>=w[i]) f[i&1][j][k]=(f[i&1][j][k]+f[(i-1)&1][j-w[i]][k])%P;
				f[i&1][j][i]=(f[i&1][j][i]+f[(i-1)&1][j][k])%P;
			}
		}
	}
	int res=0;
	for(int i=0;i<=m;i++){
		for(int j=0;j<=n;j++) res=(res+f[n&1][i][j]*(w[j]>m-i))%P;
	}
	wt('\n',res);
	return 0;
}

AGC013D Piling Up

挺典的

P4778 Counting swaps

不会的套路题/kk

ABC214G/S2OJ1504

又是我不会的/hanx

做了一天/ng

直接做显然是不行的，所以考虑转化题意，对于 \(\forall i\) ，连边 \((A_i,B_i)\) ，现在题意就变成给边染色了，这样统计的就是不合法的，考虑容斥，一个很 \(\text{naive}\) 的容斥是 总数-不合法，发现你根本做不了，所以很容易想到加强限制，让答案等于 \(\sum\limits_{i=0}^n (-1)^i\times f(i)\) ，其中 \(f(i)\) 表示钦定有 \(i\) 个位置不满足 \(C_i!=A_i,C_i!=B_i\) 的方案数，即断掉 \(i\) 条边，考虑怎么求这个东西

考虑一个环怎么做

假设不是环而是一条链，容易想到设 \(f_{i,j,0/1}\) 表示现在到了第 \(i\) 个点，断掉 \(j\) 条边，钦定第 \(i\) 条边颜色为 \(A_i/B_i\) ，转移就是：

\(f_{i,j,0}=\sum\limits_{k=1}^{i-2}f_{k,j-1,1}+\sum\limits_{k=1}^{i-1}f_{k,j-1,0}\)

\(f_{i,j,1}=\sum\limits_{k=1}^{i-1}f_{k,j-1,1}+\sum\limits_{k=1}^{i-1}f_{k,j-1,0}\)

这个可以前缀和优化成 \(O(n^2)\) 的

但是这个 \(dp\) 是不适用于环的，因为我环上的第一个点会影响到最后一个点，所以要分类讨论强制断环成链

当我第一条边染的色是 \(A_i\) 时：

初始化：\(f_{1,1,0}=1\)

对答案贡献：\(\sum\limits_{i=1}^{n}f_{i,j,0}+\sum\limits_{i=1}^{n-1}f_{i,j,1}\)

当我第一条边染的色是 \(B_i\) 时：

初始化：\(f_{1,1,1}=1\)

对答案贡献：\(\sum\limits_{i=1}^{n}f_{i,j,0}+\sum\limits_{i=1}^{n}f_{i,j,1}\)

当我第一条边断掉时：

初始化：\(\forall i ,\ f_{i,1,0}=f_{i,1,1}=[i!=1]\)

对答案贡献：\(\sum\limits_{i=1}^{n}f_{i,j,0}+\sum\limits_{i=1}^{n}f_{i,j,1}\)

这三个方程中间的转移发现和上面的链的方程的转移是一样的

然后最后写一个背包合并把所有的环合并起来就好了/hanx

因为背包合并的复杂度是 两背包大小和乘上小的那个背包大小，所以时间复杂度是正确的/hanx

code

libreoj #3144. 「APIO2019」奇怪装置

挺奇怪的一道题，不会

标签：int,void,args,rd,计数,wt,inline,dp
From： https://www.cnblogs.com/lnyx/p/17364607.html

相关文章

  • WordPress extended XML-RPC MetaWeblog API
    XML-RPCMetaWeblogAPI«WordPressCodexWordPress.orgWordPress.orgPluginsThemesPatternsLearnSupportDocumentationForumsNewsAboutGetInvolvedFivefortheFutureShowcaseMobileHostingOpenverseGetWordPressSearch......
  • Codeforces 1804H - Code Lock（状压 dp）
    对于一种排列方案，答案显然等于相邻字符在环上对应的劣弧长度之和。然后其实你可能会想到很多状压/折半搜索方法，包括但不限于枚举一半的信息然后折半搜后一半，但稍加思考会发现这些方案都避不开记录元素之间的相对顺序，而但凡涉及到这一点，复杂度都是阶乘起步。因此我们只能另辟蹊......
  • Codeforces 1799H - Tree Cutting（树形 dp）
    思考的时候一直卡在不会在低于\(O(n)\)的时间内储存一个连通块的\(siz\)有关的信息，看了洛谷题解之后才发现我真是个小丑。树形DP。对于一条我们需要操作的边\((i,fa_i)\)，我们将其分为保留子树和删除子树两种类型，对于删除子树，我们在判定其是否合法时候改为判定删除的连通块......
  • wordpress插件:代码高亮显示并配置样式(SyntaxHighlighter Evolved 3.6.2 / wordpress
    一，安装插件:SyntaxHighlighterEvolved点击插件->安装插件->输入：SyntaxHighlighter进行搜索结果显示后，找到并进行安装，如图：安装第一个安装后的效果:二，安装插件后调整样式(行高):先找到样式文件路径，当前如下:/wp-content/plugins/syntaxhighlighter/syntaxhighlighter3/......
  • [Linux]raspbian安装xrdp（远程桌面）
    1.首先换源:输入以下命令sudosed-i"s@http://deb.debian.org@https://mirrors.163.com@g"/etc/apt/sources.list2.update是更新软件列表,upgrade是更新软件。这两个命令一般是一起使用的。3.需要在Debian系统中安装xrdp，xrdpisadaemonthatsupportsMicrosoft'sRemoteD......
  • 组合计数
    组合数\(C^m_n\)=\(\dfrac{n(n-1)(n-2)\cdots(n-m+1)}{m!}\)=\(\dfrac{n!}{m!(n-m)!}\)\(C^m_n\)=\(C^m_{n-1}\)+\(C^{m-1}_{n-1}\)递推法求组合数求组合数Ⅰ\(\quad\)\(C^m_n\)=\(C^m_{n-1}\)+\(C^{m-1}_{n-1}\)//递推法求组合数模板//c[a][b]存储C......
  • 区间dp 和 树型dp
    区间dp递推方程是以区间的形式给出一般套路：枚举区间长度区间端点区间分界点然后就是想怎么去对这个区间进行一定的操作从最原始的地方开始一步步推导方程！for(i=1;i<n;i++)//区间长度为1{ for(j=1;j<=n-i;j++)//区间开头 { for(k=j;k<j+i;k++)//分界点 { f[j][......
  • 设置wordpress:关闭底部默认的facebook等链接(wordpress 6.2)
    一，默认显示:如图:说明：刘宏缔的架构森林是一个专注架构的博客，地址：https://www.cnblogs.com/architectforest     对应的源码可以访问这里获取： https://github.com/liuhongdi/     或: https://gitee.com/liuhongdi说明：作者:刘宏缔邮箱:[email protected]......
  • 【树形DP入门题】NO337 打家劫舍III
    【树形DP入门题】337.打家劫舍III小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为root。除了root之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子......
  • 设置wordpress:设置标题字号大小(wordpress 6.2)
    一，未设置之前字号过大，如图:说明：刘宏缔的架构森林是一个专注架构的博客，地址：https://www.cnblogs.com/architectforest     对应的源码可以访问这里获取： https://github.com/liuhongdi/     或: https://gitee.com/liuhongdi说明：作者:刘宏缔邮箱:3711253......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99