109徐守佳

用户名：dotcpp0787174

访问量：94

签　名：

想AC的我戴上了WA面具

等　　级
排　　名	6758
经　　验	1356
参赛次数	0
文章发表	15
年　　龄	20
在职情况	学生
学　　校	内江师范学院
专　　业	柚子厨

　　自我简介：

TA的其他文章

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

抓住那头牛! 双向BFS
浏览：19

[信息学奥赛一本通T1255-迷宫问题]（广搜) warning:方向数组从下逆时针开始
浏览：13

你可能喜欢

C语言程序设计教程（第三版）课后习题6.2 （C++代码）为什么回车不算字符

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

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

　　作者: 109徐守佳　　　　发表时间：2024-09-12 11:53:10 浏览：14　|　评论：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

108叶先毅是个小蒟蒻

%%%% orz

2024-09-12 11:53:57

109徐守佳

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.2 （C++代码）为什么回车不算字符

C二级辅导-进制转换（C语言代码）

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

C二级辅导-计负均正（C语言代码）

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

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

评论区

精彩推荐

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

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

字符串输入输出函数（Java代码）

C语言训练-立方和不等式（C语言代码）

C语言训练-素数问题（C语言代码）

最长单词（C语言代码）

C语言训练-排序问题<1> （C语言代码）

淘淘的名单（C语言代码）答案错误？？？

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

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

109徐守佳

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.2 （C++代码）为什么回车不算字符

C二级辅导-进制转换 （C语言代码）

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

C二级辅导-计负均正 （C语言代码）

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

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

评论区

精彩推荐

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

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

字符串输入输出函数 （Java代码）

C语言训练-立方和不等式 （C语言代码）

C语言训练-素数问题 （C语言代码）

最长单词 （C语言代码）

C语言训练-排序问题<1> （C语言代码）

淘淘的名单 （C语言代码）答案错误？？？

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

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

C二级辅导-进制转换（C语言代码）

C二级辅导-计负均正（C语言代码）

　　评论区

字符串输入输出函数（Java代码）

C语言训练-立方和不等式（C语言代码）

C语言训练-素数问题（C语言代码）

最长单词（C语言代码）

淘淘的名单（C语言代码）答案错误？？？