2011-08-22 15:45:24Morris
d249. 94北縣賽-1-心意相通的指數(Match)
d249. 94北縣賽-1-心意相通的指數(Match)
為了答案設置的方便所以限制只有小珠的可以旋轉
/**********************************************************************************/
/* Problem: d249 "94北縣賽-1-心意相通的指數(Match)" from */
/* Language: C */
/* Result: AC (12ms, 341KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-22 15:41:42 */
/**********************************************************************************/
#include<stdio.h>
#include<string.h>
int DP[251][251], Ans = 0;
char AnsS[251], Print[251][251];
void Find(int x, int y, int now, char *A) {
if(x == 0 || y == 0) return;
if(Print[x][y] == 1) {
Find(x-1, y-1, now-1, A);
AnsS[now] = A[x-1];
} else if(Print[x][y] == 2)
Find(x, y-1, now, A);
else
Find(x-1, y, now, A);
}
void LCS(char *A, int Al, char *B, int Bl) {
DP[0][0] = DP[1][0] = DP[0][1] = 0;
int a, b;
for(a = 0; a < Al; a++) {
for(b = 0; b < Bl; b++) {
if(A[a] == B[b])
DP[a+1][b+1] = DP[a][b]+1, Print[a+1][b+1] = 1;
else {
if(DP[a+1][b] >= DP[a][b+1])
DP[a+1][b+1] = DP[a+1][b], Print[a+1][b+1] = 2;
else
DP[a+1][b+1] = DP[a][b+1], Print[a+1][b+1] = 3;
}
}
}
if(DP[Al][Bl] >= Ans) {
Ans = DP[Al][Bl];
Find(Al, Bl, Ans-1, A);
AnsS[Ans] = '\0';
}
}
main() {
char A[502], B[502];
while(scanf("%s %s", A, B) == 2) {
int Al = strlen(A), Bl = strlen(B), a, b;
for(a = 0, b = Al; a < Al; a++, b++)
A[b] = A[a];
for(a = 0, b = Bl; a < Bl; a++, b++)
B[b] = B[a];
Ans = 0;
for(a = Al-1; a >= 0; a--)
LCS(A+a, Al, B, Bl);
puts(Ans ? AnsS : "no");
printf("%.2lf\n", (double)Ans*2/(Al+Bl));
}
return 0;
}
內容 ：
問題描述
最近日本的高中學生之間流傳著一種測驗兩個好朋友是否心意相通的方法：兩
個人分別利用七種顏色的珠子串成項鍊，再看看兩個人製作出來的項鍊的相似程
度。若這七種顏色的珠子分別以R、O、Y、G、B、I 及P 表示，請你寫一個程式來
計算兩個人心意相通的指數。
舉個例子來說，小珠和小麗分別做了兩條項鍊：
小珠的項鍊： RROYBGRB
小麗的項鍊： BRRYYBGGGG
若將這兩條項錬看成兩個字串，則其最長的相似子字串為RRYBG，(在找相似子字
串時，只要考慮珠子顏色的排列順序即可，不需考慮兩個珠子中間是否有其他不同
的珠子，如果有只要跳過即可)，但是由於項鍊串成圓形的，在比對時要考慮不同的
比對起點，來找出最長的相似子字串。例如將小珠的項鍊旋轉一下，
旋轉後小珠的項鍊： BRROYBGR
則二個字串的最長相似子字串就變成RRYBGB 了。因此，上述這兩條項鍊真正的最
長相同子字串應該是RRYBGB 才對。而這兩條項鍊間的相似程度則可以利用下式計
算得到
相似程度值= 最長相似子字串長度的二倍/兩條項鍊長度的總和
兩條項鍊長度的總和
最長相似子字串長度的二倍
同時這個值也就是兩個人心意相通的指數。
為了答案設置的方便所以限制只有小珠的可以旋轉
條件限制
1. 輸入的兩組字串皆由R、O、Y、G、B、I 及P 七種字母組成且字串長度皆小於250。
2. 如果兩組字串沒有相似的子字串，請輸出“no＂。
3. 如果兩組字串有一個以上的最長相似子字串，只要輸組任意一個最長相似子字串即可。
輸入說明
：
輸入資料為二行由R、O、Y、G、B、I 及P 組成的字串。
輸出說明
：
請輸出最長的相似子字串以及相似程度值(到小數點第二位，第三位以後四捨五
入)。
入)。
範例輸入 ：
BRRYYBGOY YYBOBRG
範例輸出 ：
YYBOBR 0.75
提示
：
出處
：
/**********************************************************************************/
/* Problem: d249 "94北縣賽-1-心意相通的指數(Match)" from */
/* Language: C */
/* Result: AC (12ms, 341KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-22 15:41:42 */
/**********************************************************************************/
#include<stdio.h>
#include<string.h>
int DP[251][251], Ans = 0;
char AnsS[251], Print[251][251];
void Find(int x, int y, int now, char *A) {
if(x == 0 || y == 0) return;
if(Print[x][y] == 1) {
Find(x-1, y-1, now-1, A);
AnsS[now] = A[x-1];
} else if(Print[x][y] == 2)
Find(x, y-1, now, A);
else
Find(x-1, y, now, A);
}
void LCS(char *A, int Al, char *B, int Bl) {
DP[0][0] = DP[1][0] = DP[0][1] = 0;
int a, b;
for(a = 0; a < Al; a++) {
for(b = 0; b < Bl; b++) {
if(A[a] == B[b])
DP[a+1][b+1] = DP[a][b]+1, Print[a+1][b+1] = 1;
else {
if(DP[a+1][b] >= DP[a][b+1])
DP[a+1][b+1] = DP[a+1][b], Print[a+1][b+1] = 2;
else
DP[a+1][b+1] = DP[a][b+1], Print[a+1][b+1] = 3;
}
}
}
if(DP[Al][Bl] >= Ans) {
Ans = DP[Al][Bl];
Find(Al, Bl, Ans-1, A);
AnsS[Ans] = '\0';
}
}
main() {
char A[502], B[502];
while(scanf("%s %s", A, B) == 2) {
int Al = strlen(A), Bl = strlen(B), a, b;
for(a = 0, b = Al; a < Al; a++, b++)
A[b] = A[a];
for(a = 0, b = Bl; a < Bl; a++, b++)
B[b] = B[a];
Ans = 0;
for(a = Al-1; a >= 0; a--)
LCS(A+a, Al, B, Bl);
puts(Ans ? AnsS : "no");
printf("%.2lf\n", (double)Ans*2/(Al+Bl));
}
return 0;
}