洛谷 p1140 相似基因 [ DP ]

https://www.luogu.com.cn/problem/P1140

题意：两个碱基对序列，4种核苷酸，简记作 A,C,G,T ，每种核苷酸各自对应时

作用不同，求最大作用。

$d[ i ][ j ][ 0/1 ]$ 表示到链 1 的 $i$ 位置，链 2 的 $j$ 位置时，末尾位置对齐或对空时的状态。

状态转移如下代码

const int INF=0x3f3f3f3f;
const int MAX=100+10;
char s1[MAX],s2[MAX];
int l1,l2,d[MAX][MAX][2];
int a[100][100];
char dn[5]={'A','C','G','T','-'};
int dc[25]={5,-1,-2,-1,-3,-1,5,-3,-2,-4,-2,-3,5,
           -2,-2,-1,-2,-2,5,-1,-3,-4,-2,-1,-INF};
void init(){
	int k=0;
	fi(i,0,5)
		fi(j,0,5)
			a[dn[i]][dn[j]]=dc[k++];
}
int main(){
	freopen("in","r",stdin);
	sf(l1);scanf("%s",s1+1);
	sf(l2);scanf("%s",s2+1);
	init();
	fi(i,1,l1+1){
		d[i][0][0]=d[i-1][0][0] + a[s1[i]]['-'];
		d[i][0][1]=-INF;
	}
	fi(i,1,l2+1){
		d[0][i][0]=d[0][i-1][0] + a['-'][s2[i]];
		d[0][i][1]=-INF;
	}
	fi(i,1,l1+1){
		fi(j,1,l2+1){
			d[i][j][0]=max(max(d[i-1][j][0]+a[s1[i]]['-'],d[i][j-1][0]+a['-'][s2[j]]),
			           max(d[i][j-1][1]+a['-'][s2[j]],d[i-1][j][1]+a[s1[i]]['-']));
			d[i][j][1]=max(d[i-1][j-1][0]+a[s1[i]][s2[j]] , d[i-1][j-1][1]+a[s1[i]][s2[j]]);
		}
	}
	pf(max(d[l1][l2][0],d[l1][l2][1]));
	return 0;
}

观察发现，第三个状态是多余的…去掉后如下…

const int INF=0x3f3f3f3f;
const int MAX=100+10;
char s1[MAX],s2[MAX];
int l1,l2,d[MAX][MAX];
int a[100][100];
char dn[5]={'A','C','G','T','-'};
int dc[25]={5,-1,-2,-1,-3,-1,5,-3,-2,-4,-2,-3,5,
           -2,-2,-1,-2,-2,5,-1,-3,-4,-2,-1,-INF};
void init(){
	int k=0;
	fi(i,0,5)
		fi(j,0,5)
			a[dn[i]][dn[j]]=dc[k++];
}
int main(){
	freopen("in","r",stdin);
	sf(l1);scanf("%s",s1+1);
	sf(l2);scanf("%s",s2+1);
	init();
	fi(i,1,l1+1)
		d[i][0]=d[i-1][0] + a[s1[i]]['-'];
	fi(i,1,l2+1)
		d[0][i]=d[0][i-1]+ a['-'][s2[i]];
	fi(i,1,l1+1)
		fi(j,1,l2+1)
			d[i][j]=max(d[i-1][j-1]+a[s1[i]][s2[j]],max(d[i][j-1]+a['-'][s2[j]],d[i-1][j]+a[s1[i]]['-']));
	pf(d[l1][l2]);
	return 0;
}