UVA - 10981(dp,map은 메모리 클래스로 사용되며 최대 메모리는 계산되지 않음)
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <set>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef unsigned long long LLU;
typedef long long LL;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
const int maxn = 110;
const int b[3][3]={
{1,1,0},{2,1,0},{0,2,2}
};
int a[maxn],d[maxn][maxn][3],n,tar,path[maxn][maxn];
map<string,int> dp;
map<string,string> pa;
int dfs(string s){
if(dp.count(s)) return dp[s];
if(s.length()==1&&s[0]==tar+'a'){
return dp[s] = 1;
}
dp[s] = 0;
for(int i=0;i<s.length()-1;i++){
string te;
for(int j=0;j<i;j++) te.push_back(s[j]);
te.push_back((char)(b[s[i]-'a'][s[i+1]-'a']+'a') );
for(int j=i+2;j<s.length();j++) te.push_back(s[j]);
if(dfs(te)){
dp[s] = 1;
pa[s] = te;
return 1;
}
}
return 0;
}
char s[maxn];
void print(string s){
printf("%s
",s.c_str());
if(s.length() == 1){return ;}
print(pa[s]);
}
int main()
{
int T;
scanf("%d",&T);
while(T--){
cin>>s;
string ss = s;
cin>>s; tar = s[0]-'a';
dp.clear(); pa.clear();
n = strlen(s);
if(dfs(ss)) print(ss);
else printf("None exist!
");
if(T) printf("
");
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
