社区讨论

感觉没问题,不知道错哪

UVA529Addition Chains参与者 1已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lo33mdu0
此快照首次捕获于
2023/10/24 00:15
2 年前
此快照最后确认于
2023/10/24 00:15
2 年前
查看原帖
输出格式也改过了,但是还是WA
loj和AcWing上也AC了,但是洛谷上WA掉了
CPP
#include <cstdio>

using namespace std;

typedef long long LL;
int n;
int path[10010];

bool dfs(int u, int depth)
{
    if (u == depth + 1) return path[u - 1] == n;
    
    for (int i = u - 1; i >= 1; --i)
        for (int j = i; j >= 1; --j)
        {
            int s = path[i] + path[j];
            if (s <= path[u - 1]) return false;
            if ((LL)s * (1ll << (depth - u + 1)) < n) return false;
            if (s > path[u - 1] && s <= n && s <= (path[u - 1] << 1))
            {
                path[u] = s;
                if (dfs(u + 1, depth)) return true;
            }
        }
    
    return false;
}

int main()
{
    int T = 0;
    while (scanf("%d", &n), n)
    {
        ++ T;
        if (T > 1) puts("");
        int depth = 1;
        path[1] = 1;
        while (!dfs(2, depth)) ++ depth;
        
        for (int i = 1; i < depth; ++i)
            printf("%d ", path[i]);
        printf("%d", path[depth]);
    }
    return 0;
}

回复

1 条回复,欢迎继续交流。

正在加载回复...