P1019 단어 끝 말 잇 기
1763 단어 알고리즘
단어 끝 말 잇 기 는 우리 가 자주 하 는 성어 끝 말 잇 기 와 비슷 한 게임 이다. 현재 우 리 는 한 개의 단 어 를 알 고 있 으 며 시작 하 는 자 모 를 정 하여 이 자모 로 시작 하 는 가장 긴 '용' (단어 마다 '용' 에 두 번 까지 나타 나 는 것) 을 요구한다. 두 단어 가 연결 되 었 을 때 그 겹 치 는 부분 은 일부분 으로 합 쳐 야 한다. 예 를 들 어 beastbeast 화해시키다 astonishastonish ，용 한 마리 로 연결 되면 beastonishbeastonish ，또한 인접 한 두 부분 에 포함 관계 가 존재 할 수 없다. 예 를 들 어 atat 화해시키다 atideatide 서로 연결 할 수 없다.
입 출력 형식
입력 형식:
입력 한 첫 번 째 행동 의 단독 정수 nn ( n \le 20n≤20 )아래 nn 줄 마다 단어 가 있 습 니 다. 입력 한 마지막 행동 은 하나의 문자 로 '용' 으로 시작 하 는 자 모 를 표시 합 니 다. 이 자모 로 시작 하 는 '용' 이 반드시 존재 한다 고 가정 할 수 있 습 니 다.
출력 형식:
이 자모 로 시작 하 는 가장 긴 '용' 의 길 이 를 출력 하기 만 하면 된다.
입 출력 샘플
샘플 입력 \ # 1: 복제 하 다.
5
at
touch
cheat
choose
tact
a
출력 샘플 \ # 1: 복제 하 다.
23
#include
#include
#include
#include
using namespace std;
int n,use[20],maxlen = 0;
string s[20],c;
int has_len(string a, string b){
int len = min(a.length(),b.length());
for(int i = 1; i < len; i ++){// 1
int flag = 1;
for(int j = 0; j < i; j ++){
if(a[a.length() - i +j] != b[j])// -》
flag = 0;
}
if(flag) return i;//
}
return 0;
}
void link(string str, int l){//dfs
maxlen = max(l,maxlen);
for(int i = 0; i < n; i++)
{
if(use[i] >=2 ) continue;
int k = has_len(str,s[i]);
if(k > 0){
use[i] ++;
link(s[i],s[i].length()+l-k);
use[i] --;
}
}
}
int main() {
cin >> n;
for(int i = 0; i < n; i ++){
cin >> s[i];
}
cin >> c;
link(' '+c,1);
cout << maxlen;
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
