POJ 2248 - Addition Chains [DFS, 반복 검색 심화]
1627 단어 DFS알고리즘 학습 문제 풀이 기록
제목: 현재 하나의 배열 중 a [1] = 1, a [m] = n, 그리고 a [1] < a [2] <..........................................................그 중 1 < = n < = 9
대체적인 사고방식: 만약 우리 가 DFS 에 따라 직접 검색 한다 면 모두 n 이 있 습 니 다!하나의 노드 가 매우 오래 걸 립 니 다. 이 럴 때 우 리 는 반복 적 으로 검색 을 강화 할 수 있 습 니 다. 모든 검색 은 검색 깊이 를 제한 하고 검색 깊이 를 한 단계 씩 늘 려 서 답 을 찾 을 때 까지 알 수 있 습 니 다.
코드:
#include
#include
#include
#include
using namespace std;
const int MAXN = 110;
bool vis[MAXN];
int ans[MAXN];
int maxd,n;
bool DFS(int d){
if(d > maxd){
if(ans[maxd] == n) return true;
else return false;
}
memset(vis,0,sizeof(vis));
for(int i = d - 1; i >= 1; i--){
for(int j = d - 1; j >= 1; j--){
if(ans[i] + ans[j] <= ans[d - 1]) break;
if(!vis[ans[i] + ans[j]] && ans[i] + ans[j] <= n){
ans[d] = ans[i] + ans[j];
vis[ans[d]] = 1;
if(DFS(d + 1)) return true;
}
}
}
return false;
}
int main(int argc, char const *argv[])
{
while(~scanf("%d",&n) && n){
bool ok = false;
ans[1] = 1;
//ans[0] = 0;
if(n == 1) { cout << "1" << endl; continue; }
for(maxd = 2; ; maxd++){
memset(vis,0,sizeof(vis));
if(DFS(2)) { ok = true; break; }
}
//cout << maxd << endl;
if(ok){
for(int i = 1; i < maxd; i++) cout << ans[i] << " ";
cout << ans[maxd] << endl;
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BOJ] 5568 카드 놓기아이디어 Level이 0일 때, 즉 아직 카드를 고르지 않았을 때 StringBuilder를 생성하고 sb에 고른 카드를 담도록 하였다. 이후 해당 노드 탐색을 종료하면 sb에 담은 카드를 삭제해 주었다....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
