虹口基础微网站开发,网站目录 index.html,河北网站开发联系电话,网页设计与制作书籍正题
题目链接:https://www.luogu.com.cn/problem/P1758 题目大意
给出一个大小为nnn和一个大小为mmm的栈#xff0c;每次选择一个栈弹出栈顶然后记录这个字母#xff0c;求所有弹出序列的弹出方案的二次方和。 1≤n,m≤5001\leq n,m\leq 5001≤n,m≤500 解题思路
二次方和…正题
题目链接:https://www.luogu.com.cn/problem/P1758 题目大意
给出一个大小为nnn和一个大小为mmm的栈每次选择一个栈弹出栈顶然后记录这个字母求所有弹出序列的弹出方案的二次方和。
1≤n,m≤5001\leq n,m\leq 5001≤n,m≤500 解题思路
二次方和可以看为取出方案相同的对数。
然后就是很简单的dpdpdp了设fi,j,kf_{i,j,k}fi,j,k表示都取出了iii个在第一个栈里分开取了j/kj/kj/k个然后滚动。
时间复杂度O(nmn2)O(nmn^2)O(nmn2) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N510,P1024523;
int n,m,f[N*2][N][N];
char s[N],t[N];
int main()
{scanf(%d%d,n,m);scanf(%s,s1);scanf(%s,t1);f[0][0][0]1;for(int i1;inm;i)for(int j0;jmin(n,i);j)for(int k0;kmin(n,i);k){f[i1][j][k]0;if(s[j]s[k]jk)(f[i1][j][k]f[~i1][j-1][k-1])%P;if(s[j]t[i-k]ji-k)(f[i1][j][k]f[~i1][j-1][k])%P;if(t[i-j]s[k]ki-j)(f[i1][j][k]f[~i1][j][k-1])%P;if(t[i-j]t[i-k]i-ji-k)(f[i1][j][k]f[~i1][j][k])%P;}printf(%d\n,f[(nm)1][n][n]);return 0;
}
