社区讨论
关于剪枝dfs的复杂度
P1433吃奶酪参与者 9已保存回复 8
讨论操作
快速查看讨论及其快照的属性，并进行相关操作。
- 当前回复
- 8 条
- 当前快照
- 1 份
- 快照标识符
- @mi6txjib
- 此快照首次捕获于
- 2025/11/20 10:46 4 个月前
- 此快照最后确认于
- 2025/11/20 10:46 4 个月前
这个题普遍的做法只是简单的cost>mincost? prune
但是这个dfsBnB的复杂度显然是不对的。随手出了一组数据，绝大部分的搜索题解全部挂了，只有状压dp的那个复杂度是对的。
预处理距离也没有什么效果，复杂度都是错的。但是有些还加了其他剪枝的似乎过了这个数据，暂时不知道是不是对的。
input
CPP15
0 0
1 1
1 -1
-1 1
-1 -1
2 2
2 0
2 -2
0 -2
-2 -2
-2 0
-2 2
0 2
1 3
1 4
output
CPP21.73
那么让这种复杂度明显错误的算法过去是否合理？
回复
共 8 条回复，欢迎继续交流。
正在加载回复...