BZOJ 2423 DP

BZOJ 2423 - DP

第一问是经典DP,直接做就可以了(设(f[i][j])(X)串考虑到(i)(Y)串考虑到(j),且不强制选(i)(j)的方案数)。然后第二问。分几种情况讨论一下(可能看起来有点不优美……): 设(g[i][j])为方案数,则

I. (A[i]=B[j])

  • (g[i][j]=g[i-1][j-1]+ k_1cdot g[i-1][j]+ k_2cdot g[i][j-1])
  • (f[i][j]=f[i-1][j])时,(k_1=1),否则(k_1=0)(k_2)同理。
  • 首先,加上(g[i-1][j-1])是显然的。
  • 然后,如果同时加上(g[i-1][j])(g[i][j-1]),那么它们肯定不会重复,因为假设重复,那么就意味着必然有(LCS(i-1, j-1)=f[i][j]),而这是显然不对的。

II. (A[i] e B[j])

  • (g[i][j]=k_1cdot g[i][j-1]+k_1cdot g[i-1][j]-k_3cdot g[i-1][j-1])
  • 注意(g[i-1][j-1])前面是减号。
  • 因为(A[i]=B[j])时,必然选了(A[i])(B[j]),所以三种情况互相独立,直接加就行了。
  • (A[i] e B[j])时,(g[i-1][j-1])可能会造成重复加。容斥一下就行了。

代码1(未加滚动数组)

// BZOJ 2423

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

 const int N=5000+5, mod=100000000;

 #define rep(i,a,b) for (int i=a; i<=b; i++)
 #define read(x) scanf("%d", &x)
 #define fill(a,x) memset(a, x, sizeof(a))

 short f[N][N];
 int g[N][N], k1, k2, k3;
 char x[N], y[N];

int main()
{
	scanf("%s%s", x+1, y+1);
	int lx=strlen(x+1)-1, ly=strlen(y+1)-1;
	f[0][0]=f[0][1]=f[1][0]=0;
	rep(i,1,lx) 
	  rep(j,1,ly) 
		if (x[i]==y[j]) f[i][j]=f[i-1][j-1]+1; 
		else f[i][j]=max(f[i-1][j], f[i][j-1]);
	rep(i,0,ly) g[0][i]=1; 
	rep(i,0,lx) g[i][0]=1;
	rep(i,1,lx)
	  rep(j,1,ly) {
	  	if (f[i][j] == f[i-1][j]) k1 = 1; else k1 = 0;
	    if (f[i][j] == f[i][j-1]) k2 = 1; else k2 = 0;
	    if (x[i] == y[j]) k3 = 1;
	    if (x[i] != y[j] && f[i][j] != f[i-1][j-1]) k3 = 0;
	    if (x[i] != y[j] && f[i][j] == f[i-1][j-1]) k3 = -1;
	    g[i][j] = (k1*g[i-1][j] + k2*g[i][j-1] + k3*g[i-1][j-1]) % mod;
	  }
	printf("%d
%d
", f[lx][ly], g[lx][ly]);

	return 0;
}


代码2(加滚动数组,(略丑))

// BZOJ 2423

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

 const int N=5000+5, mod=100000000;

 #define rep(i,a,b) for (int i=a; i<=b; i++)
 #define read(x) scanf("%d", &x)
 #define fill(a,x) memset(a, x, sizeof(a))

 short f[N][N];
 int g[2][N], k1, k2, k3;
 char x[N], y[N];

int main()
{
	scanf("%s%s", x+1, y+1);
	int lx=strlen(x+1)-1, ly=strlen(y+1)-1;
	f[0][0]=f[0][1]=f[1][0]=0;
	rep(i,1,lx) 
	  rep(j,1,ly) 
		if (x[i]==y[j]) f[i][j]=f[i-1][j-1]+1; 
		else f[i][j]=max(f[i-1][j], f[i][j-1]);
	rep(i,0,ly) g[0][i]=1; 
    int now=1, pre=0;
	rep(i,1,lx) {
	  rep(j,1,ly) {
	  	g[now][0]=1;
	  	if (f[i][j] == f[i-1][j]) k1 = 1; else k1 = 0;
	    if (f[i][j] == f[i][j-1]) k2 = 1; else k2 = 0;
	    if (x[i] == y[j]) k3 = 1;
	    if (x[i] != y[j] && f[i][j] != f[i-1][j-1]) k3 = 0;
	    if (x[i] != y[j] && f[i][j] == f[i-1][j-1]) k3 = -1;
	    g[now][j] = (k1*g[pre][j] + k2*g[now][j-1] + k3*g[pre][j-1]) % mod;
	  }
	  now^=1; pre^=1;
	}
	printf("%d
%d
", f[lx][ly], g[pre][ly]);

	return 0;
}

原文地址:https://www.cnblogs.com/yearwhk/p/5125429.html