做网站客户,性价比最高网站建设哪里好,wordpress网址采集,网站开发程序介绍传送门 首先那个\(O(n^2)\)的dp都会吧,不会自己找博客或者问别人,或是去做模板题(误) 对以下内容不理解的,强势推荐flash的博客 我们除了原来记录最长上升子序列的\(f_{i,j}\),再记\(g_{i,j}\)表示到\(i,j\)时的最长上升子序列个数,同时设两个字符串为\(A,B\) 若\(A_iB_j\) ,则…传送门 首先那个\(O(n^2)\)的dp都会吧,不会自己找博客或者问别人,或是去做模板题(误) 对以下内容不理解的,强势推荐flash的博客 我们除了原来记录最长上升子序列的\(f_{i,j}\),再记\(g_{i,j}\)表示到\(i,j\)时的最长上升子序列个数,同时设两个字符串为\(A,B\) 若\(A_iB_j\) ,则有\(f_{i,j}f_{i-1,j-1}1,g_{i,j}g_{i-1,j-1}\) 否则\(f_{i,j}max(f_{i-1,j},f_{i,j-1}),g_{i,j}\)的话看能否从\(f_{i-1,j}\)或\(f_{i,j-1}\)转移,如果可以就加上对应的\(g\) 注意,如果\(f_{i,j}f_{i-1,j-1}\)(等价于\(f_{i,j}f_{i-1,j}f_{i,j-1}\)),那么\(g_{i-1,j-1}g_{i-1,j}g_{i,j-1}\frac{1}{2}g_{i,j}\),所以要减去\(g_{i-1,j-1}\) 至于为什么,yyb都没写,我也不好说.,反正要么感性理解(雾),要么打表手玩.还不理解就戳flash吧qwq // luogu-judger-enable-o2
#includebits/stdc.h
#define LL long long
#define il inline
#define re register
#define db double
#define max(a,b) ((a)(b)?(a):(b))using namespace std;
const int N500010,mod100000000;
il LL rd()
{re LL x0,w1;re char ch0;while(ch0||ch9) {if(ch-) w-1;chgetchar();}while(ch0ch9) {x(x3)(x1)(ch^48);chgetchar();}return x*w;
}
int f[2][N],g[2][N],n,m;
char cc[N],ss[N];int main()
{scanf(%s%s,cc1,ss1);nstrlen(cc1)-1,mstrlen(ss1)-1;g[0][0]g[1][0]1;for(int j1;jm;j) g[0][j]1;int nw1,la0;for(int i1;in;i){for(int j1;jm;j){f[nw][j]g[nw][j]0;if(cc[i]ss[j]) f[nw][j]f[la][j-1]1,g[nw][j]g[la][j-1];else f[nw][j]max(f[nw][j-1],f[la][j]);if(f[nw][j]f[la][j]) g[nw][j]g[la][j];if(f[nw][j]f[nw][j-1]) g[nw][j]g[nw][j-1];if(f[nw][j]f[la][j-1]) g[nw][j]-g[la][j-1];g[nw][j]%mod;}swap(nw,la);}printf(%d\n%d\n,f[la][m],g[la][m]);return 0;
}转载于:https://www.cnblogs.com/smyjr/p/9609291.html
