一開始用的DFS,無限TLE,貼丑代碼
//version 1 TLE #include#include #include #define MAX_INT 2147483647 #define MAXN 105 using namespace std; int Map[5][5] = { {0,-3,-4,-2,-1}, {-3,5,-1,-2,-1}, {-4,-1,5,-3,-2}, {-2,-2,-3,5,-2}, {-1,-1,-2,-2,5}, }; int seq1[MAXN],seq2[MAXN],Max,n1,n2; int ref(char c) { switch (c) { case 'A': return 1; case 'C': return 2; case 'G': return 3; case 'T': return 4; } } void dfs(int id1,int id2,int sum) { if(id2 <= n2 + 1) { if(id2 == n2 + 1) { for(int i = id1;i <= n1;i ++) sum += Map[seq1[i]][0]; Max = max(Max,sum); return ; } int limi = n1 - n2 + id2,tsum = sum; for(int i = id1;i <= limi;i ++) { if(i > id1) tsum += Map[seq1[i-1]][0]; dfs(i + 1 , id2 + 1 , tsum + Map[seq1[i]][seq2[id2]]); } } } int main() { freopen("./1080.in" , "r" , stdin); int T,i,j; char c; cin>>T; while(T --) { scanf("%d%c",&n1,&c); for(i = 1;i <= n1;i ++) { scanf("%c",&c); seq1[i] = ref(c); } scanf("%d%c",&n2,&c); for(i = 1;i <= n2;i ++) { scanf("%c",&c); seq2[i] = ref(c); } if(n1 < n2) { for(int i = 1;i <= n1;i ++) swap(seq1[i] , seq2[i]); for(int i = n1 + 1;i <= n2;i ++) seq1[i] = seq2[i]; swap(n1 , n2); } Max = -MAX_INT; dfs(1,1,0); cout<
之後冥思苦想了好久,兩個序列,開始沒有想到變形的LCS(最長公共子序列),只是試著寫狀態轉移方程,最後就寫成了那個dp[i][j] = max(dp[i-1][j-1] ````,dp[i-1][j]`````,dp[i][j-1]```)的樣子,這時一看才明白這是LCS思想,但是一開始確實是瞎寫的,可能碰巧了吧=。=,最後注意這種情況:dp[0][x],當一個序列之前都用0補上的話,在循環過程中是沒辦法得到結果的,只能預先處理,切記!/* poj 1080 268K 0MS */ #include#include #include #define MAXN 105 #define MAX_INT 2147483647 using namespace std; int Map[5][5] = { {0,-3,-4,-2,-1}, {-3,5,-1,-2,-1}, {-4,-1,5,-3,-2}, {-2,-2,-3,5,-2}, {-1,-1,-2,-2,5}, }; int seq1[MAXN],seq2[MAXN],dp[MAXN][MAXN],n1,n2; int ref(char c) { switch (c) { case 'A': return 1; case 'C': return 2; case 'G': return 3; case 'T': return 4; } } int calc() { memset(dp , 0 , sizeof(dp)); for(int i = 1;i <= n1;i ++) dp[i][0] = dp[i-1][0] + Map[seq1[i]][0]; for(int i = 1;i <= n2;i ++) dp[0][i] = dp[0][i-1] + Map[0][seq2[i]]; for(int i = 1;i <= n1;i ++) for(int j = 1;j <= n2;j ++) dp[i][j] = max(dp[i-1][j-1] + Map[seq1[i]][seq2[j]] , max(dp[i-1][j] + Map[seq1[i]][0] , dp[i][j-1] + Map[0][seq2[j]]) ); return dp[n1][n2]; } int main() { int T,i,j; char c; cin>>T; while(T --) { scanf("%d%c",&n1,&c); for(i = 1;i <= n1;i ++) { scanf("%c",&c); seq1[i] = ref(c); } scanf("%d%c",&n2,&c); for(i = 1;i <= n2;i ++) { scanf("%c",&c); seq2[i] = ref(c); } cout<