1

我有这个功能，显然它会导致我的程序崩溃：

long long todos(long long x,long long i) {
  x ^= (1 << i);
  long long aux = i - 1;
  if(aux >= 0) x ^= (1 << aux);
  aux = i - 4;
  if(aux >= 0) x ^= (1 << aux);
  aux = i + 1;
  if(aux < 16) x ^= (1 << aux);
  aux = i + 4;
  if(aux < 16) x ^= (1 << aux);
  return x;
}

我不明白为什么当我更改所有^= (for&= ~(时它运行得非常好（尽管我得到的输出不同）。这种行为有什么合乎逻辑的解释吗？

如果您需要整个代码：http: //ideone.com/Z7qoof

4

2 回答 2

1

看起来你的dp()函数递归得很深。考虑到调用dp(3)可以用你的顺序评估所有 65536 个可能的位板^，而你&~的调用dp(k)只会在数字上评估之前的位板k。请注意，您是mat按顺序填写的main()；如果您之前仅在数字上依赖位板k，您将不会非常深入地递归。

编辑：至于解决这个问题，您可能认为动态规划是有向无环图中的最短路径。问题是你这里没有无环图。您正在执行深度优先搜索以在此处找到最短路径，这不起作用。尝试用广度优先搜索或 Dijkstra 算法替换它。

于 2012-11-27T12:57:37.183 回答
0

我的猜测是这条线崩溃了：

cout << mat[bs.to_ulong()] << endl;

由于 bs 大于 1<<16 的预留空间

ps 为什么对所有内容都使用 long long 数据类型？long long 是 64 位的。你做的大多数事情都可以用一个短整数来完成

于 2012-11-27T12:56:44.700 回答