AcWing 170. 加成序列(搜索)

迭代加深

原题链接

感悟:之前用紫书学了下迭代加深,自我感觉应该还是可以的,这次在来实践的时候才发现,除了知道大概要怎么做外,其他的全无头绪。很难受。这道题还是简单题啊!!!从这道题开始总结经验吧,还有老师讲的很好啊。

题型基本框架
  • 数据的存储状态 path[ ]
  • 剪枝
    -- 枚举对象的顺序
    -- 判重
  • int maxd; //限定的深度
    for(maxd = 1; ; maxd++)
       if(dfs(1, maxd)) break;
    
本题思路
  • path[ ] 里储存那些1-n的数据
  • 枚举path里已经存在的两个数来获取(1 -- n 之间)新的数,且从大到小
  • 判重:看加出来新的数是否用过了,用过则不用了(前面两个数相加会产生相同的数)

ACcode

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 105;
int X[N];
int n;

bool dfs(int d, int maxd)
{
    if(d == maxd) return X[d - 1] == n;
    
    bool st[N] = { false };
    for(int i = d-1; i >= 0; i--)
        for(int j = i; j >= 0; j--)
        {
            int s = X[i] + X[j];
            if(s > n || s <= X[d-1] || st[s]) continue;
            st[s] = true;
            
            X[d] = s;
            if(dfs(d+1, maxd)) return true;
        }
    
    return false;
}

int main()
{
    X[0] = 1;
    while(cin >> n, n)
    {
        int maxd;
        for(maxd = 1; ; maxd++) {
            if(dfs(1, maxd)) break;
        }
        for(int i = 0; i < maxd; i++) cout << X[i] << " ";
        cout << endl;
    }
    return 0;
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容