109徐守佳

用户名：dotcpp0787174

访问量：1100

签　名：

想AC的我戴上了WA面具

等　　级
排　　名	884
经　　验	3544
参赛次数	3
文章发表	30
年　　龄	20
在职情况	学生
学　　校	内江师范学院
专　　业	虹夏虹夏虹

　　自我简介：

TA的其他文章

二分直接用现成的STL:lower_bound/upper_bound(新增手写二分)
浏览：60

[信息学奥赛一本通T1247-河中跳房子] 二分答案
浏览：52

[信息学奥赛一本通T1240-查找最接近的元素] 依旧是STL
浏览：38

你可能喜欢

A+B for Input-Output Practice (VII) （C++代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

[信息学奥赛一本通T1678-Addition Chains]迭代加深？打表！

　　作者: 109徐守佳　　　　发表时间：2024-09-12 11:53:10 浏览：32　|　评论：2　

原题链接：信息学奥赛一本通T1678-Addition Chains

# 迭代加深
###### tip：不知道为啥会TLE一个点，打表过了
```cpp

#include<bits/stdc++.h>
#define ULL unsigned long long
#define LL long long
#define PII pair<int,int>
using namespace std;
const int N = 3 * 1e6 + 10,M = 2 * 1e3 + 10,inf = 0x3f3f3f3f;

int n;
int path[110];
bool dfs(int u,int depth) //u-当前层数，depth-能迭代的最大层数
{
    if(u > depth) return false;//如果超过最大层数，返回false
    // if(f(n) > depth) return false; 
    if(path[u-1] == n) return true; 
    //最后一层等于n找到合法解，返回true
    bool st[110]={0};
    for(int i=0;i<u;i++) // 找最小字典序，则从存储的序列从小到大枚举
    {
        for(int j=0;j<=i;j++)
        {
            int s = path[i] + path[j]; //算出前两个数的总和
            if(s > n || s <= path[u-1] || st[s]) continue;
            //前两个数之和大于最后需要的数或者和比前一个数小(序列严格单调递增)或者已经访问过，则直接叉掉
            st[s] = true; //标记这个和出现过,以免重复搜索
            path[u] = s; //将这个和记入路径里
            if(dfs(u+1,depth)) return true; //继续访问下一层，也就是搜索下一个该加到序列的数，直到搜到合法解形成连锁反应
            st[s] = false; //回溯
        }
    }
    return false; //没找到，返回false
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    path[0] = 1;//赋初值
    while(cin>>n,n)
    {
        int depth = 1; 
        while(!dfs(1,depth)) depth++;//迭代加深，找最小长度的答案
        for(int i=0;i<depth;i++) cout<<path[i]<<' ';
        cout<<endl;
    }
    // while(cin>>n)
    // {
    //     if(n==0) return 0;
    //     for(int i=0;i<ans[n].size();i++)
    //     {
    //         printf("%d ",ans[n][i]);
    //     }
    //     printf("\n");
    // }
    return 0;
}
// vector<vector<int>> ans = {  
//         {0},
//         {1},  
//         {1, 2},  
//         {1, 2, 3},  
//         {1, 2, 4},  
//         {1, 2, 3, 5},  
//         {1, 2, 3, 6},  
//         {1, 2, 3, 4, 7},  
//         {1, 2, 4, 8},  
//         {1, 2, 3, 6, 9},  
//         {1, 2, 3, 5, 10},  
//         {1, 2, 3, 4, 7, 11},  
//         {1, 2, 3, 6, 12},  
//         {1, 2, 3, 5, 8, 13},  
//         {1, 2, 3, 4, 7, 14},  
//         {1, 2, 3, 5, 10, 15},  
//         {1, 2, 4, 8, 16},  
//         {1, 2, 4, 8, 9, 17},  
//         {1, 2, 3, 6, 9, 18},  
//         {1, 2, 3, 4, 8, 11, 19},  
//         {1, 2, 3, 5, 10, 20},  
//         {1, 2, 3, 4, 7, 14, 21},  
//         {1, 2, 3, 4, 7, 11, 22},  
//         {1, 2, 3, 5, 10, 13, 23},  
//         {1, 2, 3, 6, 12, 24},  
//         {1, 2, 3, 5, 10, 15, 25},  
//         {1, 2, 3, 5, 8, 13, 26},  
//         {1, 2, 3, 6, 9, 18, 27},  
//         {1, 2, 3, 4, 7, 14, 28},  
//         {1, 2, 3, 4, 7, 11, 18, 29},  
//         {1, 2, 3, 5, 10, 15, 30},  
//         {1, 2, 3, 4, 7, 14, 17, 31},  
//         {1, 2, 4, 8, 16, 32},
//         {1,2,4,8,16,17,33},
//         {1, 2, 4, 8, 9, 17, 34},  
//         {1, 2, 3, 4, 7, 14, 21, 35},  
//         {1, 2, 3, 6, 9, 18, 36},  
//         {1, 2, 3, 5, 8, 16, 21, 37},  
//         {1, 2, 3, 4, 8, 11, 19, 38},  
//         {1, 2, 3, 5, 8, 13, 26, 39},  
//         {1, 2, 3, 5, 10, 20, 40},  
//         {1, 2, 3, 5, 10, 20, 21, 41},  
//         {1, 2, 3, 4, 7, 14, 21, 42},  
//         {1, 2, 3, 5, 10, 20, 23, 43},  
//         {1, 2, 3, 4, 7, 11, 22, 44},  
//         {1, 2, 3, 5, 10, 15, 30, 45},  
//         {1, 2, 3, 5, 10, 13, 23, 46},  
//         {1, 2, 3, 4, 7, 10, 20, 27, 47},  
//         {1, 2, 3, 6, 12, 24, 48},  
//         {1, 2, 3, 6, 12, 24, 25, 49},  
//         {1, 2, 3, 5, 10, 15, 25, 50},  
//         {1, 2, 3, 6, 12, 24, 27, 51},  
//         {1, 2, 3, 5, 8, 13, 26, 52},  
//         {1, 2, 3, 5, 6, 12, 24, 29, 53},  
//         {1, 2, 3, 6, 9, 18, 27, 54},  
//         {1, 2, 3, 4, 7, 11, 22, 33, 55},  
//         {1, 2, 3, 4, 7, 14, 28, 56},  
//         {1, 2, 3, 4, 7, 14, 28, 29, 57},  
//         {1, 2, 3, 4, 7, 11, 18, 29, 58},  
//         {1, 2, 3, 4, 7, 14, 28, 31, 59},  
//         {1, 2, 3, 5, 10, 15, 30, 60},  
//         {1, 2, 3, 5, 7, 14, 28, 33, 61},  
//         {1, 2, 3, 4, 7, 14, 17, 31, 62},  
//         {1, 2, 3, 4, 7, 14, 21, 42, 63},  
//         {1, 2, 4, 8, 16, 32, 64},  
//         {1, 2, 4, 8, 16, 32, 33, 65},  
//         {1, 2, 4, 8, 16, 17, 33, 66},  
//         {1, 2, 3, 4, 8, 16, 32, 35, 67},  
//         {1, 2, 4, 8, 9, 17, 34, 68},  
//         {1, 2, 3, 5, 8, 16, 32, 37, 69},  
//         {1, 2, 3, 4, 7, 14, 21, 35, 70},  
//         {1, 2, 3, 4, 7, 8, 16, 32, 39, 71},  
//         {1, 2, 3, 6, 9, 18, 36, 72},  
//         {1, 2, 3, 6, 9, 18, 36, 37, 73},  
//         {1, 2, 3, 5, 8, 16, 21, 37, 74},  
//         {1, 2, 3, 5, 10, 15, 25, 50, 75},  
//         {1, 2, 3, 4, 8, 11, 19, 38, 76},  
//         {1, 2, 4, 5, 9, 18, 36, 41, 77},  
//         {1, 2, 3, 5, 8, 13, 26, 39, 78}, 
//         {1, 2, 3, 4, 7, 9, 18, 36, 43, 79},  
//         {1, 2, 3, 5, 10, 20, 40, 80},  
//         {1, 2, 3, 5, 10, 20, 40, 41, 81},  
//         {1, 2, 3, 5, 10, 20, 21, 41, 82},  
//         {1, 2, 3, 5, 10, 20, 40, 43, 83},  
//         {1, 2, 3, 4, 7, 14, 21, 42, 84},  
//         {1, 2, 3, 5, 10, 20, 40, 45, 85},  
//         {1, 2, 3, 5, 10, 20, 23, 43, 86},  
//         {1, 2, 3, 4, 7, 10, 20, 40, 47, 87},  
//         {1, 2, 3, 4, 7, 11, 22, 44, 88},  
//         {1, 2, 3, 4, 7, 11, 22, 44, 45, 89},  
//         {1, 2, 3, 5, 10, 15, 30, 45, 90},  
//         {1, 2, 3, 4, 7, 11, 22, 44, 47, 91},  
//         {1, 2, 3, 5, 10, 13, 23, 46, 92},  
//         {1, 2, 3, 4, 7, 14, 17, 31, 62, 93},  
//         {1, 2, 3, 4, 7, 10, 20, 27, 47, 94}, 
//         {1, 2, 3, 4, 7, 11, 22, 44, 51, 95},   
//         {1, 2, 3, 6, 12, 24, 48, 96},        
//         {1, 2, 3, 6, 12, 24, 48, 49, 97},    
//         {1, 2, 3, 6, 12, 24, 25, 49, 98}, 
//         {1, 2, 3, 6, 12, 24, 48, 51, 99},    
//         {1, 2, 3, 5, 10, 15, 25, 50, 100}
// };
```

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

036叶洪鑫

汲取力量！！！

2024-09-12 13:08:44

yxy

%%%% orz

2024-09-12 11:53:57

109徐守佳

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

A+B for Input-Output Practice (VII) （C++代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

[信息学奥赛一本通T1678-Addition Chains]迭代加深？打表！

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题12.1 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

简单的a+b （C语言代码）

剔除相关数（C语言代码）

计算质因子（C++代码）

输出正反三角形（C语言代码）格式错误！！！

A+B for Input-Output Practice (V) （C语言代码）

简单的a+b （C语言代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

1009题解

109徐守佳

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

A+B for Input-Output Practice (VII) （C++代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】 （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

[信息学奥赛一本通T1678-Addition Chains]迭代加深？打表！

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题12.1 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

简单的a+b （C语言代码）

剔除相关数 （C语言代码）

计算质因子 （C++代码）

输出正反三角形 （C语言代码）格式错误！！！

A+B for Input-Output Practice (V) （C语言代码）

简单的a+b （C语言代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】 （C语言代码）

1009题解

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

　　评论区

剔除相关数（C语言代码）

计算质因子（C++代码）

输出正反三角形（C语言代码）格式错误！！！

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）