题目样例、手动样例都能过,为什么提交却WA
查看原帖
题目样例、手动样例都能过,为什么提交却WA
88339
罗小黑小鱼楼主2021/9/5 15:28

请求大佬帮忙康康QwQ

代码如下

#include<bits/stdc++.h>
using namespace std;
#define int long long
map<char,int>x;
char a[105],b[105];
int f[105][105],lena,lenb,sum[2][105];
bool p;
int q[5][5]={
	{5,-1,-2,-1,-3},
	{-1,5,-3,-2,-4},
	{-2,-3,5,-2,-2},
	{-1,-2,-2,5,-1},
	{-3,-4,-2,-1,0}
};
signed main(){
	//freopen("1.in","r",stdin);
	for(int i=0;i<=104;i++)
		for(int j=0;j<=104;j++)
			f[i][j]=-1e9;
	f[0][0]=0;
	x['A']=0;
	x['C']=1;
	x['G']=2;
	x['T']=3;
	x['-']=4; 
	scanf("%lld %s\n",&lena,a);
	scanf("%lld %s",&lenb,b);
	for(int i=lena;i>=1;i--) a[i]=a[i-1];
	for(int i=lenb;i>=1;i--) b[i]=b[i-1];
	for(int i=1;i<=lena;i++) sum[0][i]=sum[0][i-1]+q[4][x[a[i]]],f[i][0]=sum[0][i];   //赋初值 
	for(int i=1;i<=lenb;i++) sum[1][i]=sum[1][i-1]+q[4][x[b[i]]],f[0][i]=sum[1][i];   //赋初值 
	//以上为求连续 - + 字母 的前缀相似度, 
	for(int i=1;i<=lena;i++){
		for(int j=1;j<=lenb;j++){
			int t,r,u;
			char a_,b_;//都是过程变量 
			if(i>j) p=0,t=j,r=i;
			else p=1,t=i,r=j;
			for(int k=t;k<=r;k++){//枚举最后一个较短串字符对应哪一个较长串字符 
				if(p) u=f[t-1][k-1],a_=a[t],b_=b[k];
				else u=f[k-1][t-1],a_=a[k],b_=b[t];
				f[i][j]=max(f[i][j],u+q[x[a_]][x[b_]]+sum[p][r]-sum[p][k]);//DP 
			}
		}
	}
	//for(int i=1;i<=lena;i++){
	//	for(int j=1;j<=lenb;j++){
	//		cout<<i<<" "<<j<<":"<<f[i][j]<<endl;
	//	}
	//}
	cout<<f[lena][lenb];
	return 0;
}

到底是状态转移方程的问题呢还是实现的问题,请求解答。

2021/9/5 15:28
加载中...