社区讨论
感觉没问题,不知道错哪
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 条回复,欢迎继续交流。
正在加载回复...