给定一个二维数组，从 (0,0) 开始，在正 x 和 y 轴上向无穷大前进。给定一个数字 k>0 ，找到从 (0,0) 可到达的单元格数，使得在每一时刻 -> x 的数字总和 + y <=k 的数字总和。可以向上、向下、向左或向右移动。给定 x,y>=0 。
Dfs 给出了答案，但对于较大的 k 值来说还不够。任何人都可以为此提供更好的算法来帮助我吗？
问问题
152 次
1 回答
0
我认为他们要求您计算通过 k>=x+y 可到达的单元格数 (x,y)。例如，如果 x=1，则 y 可以取 0 到 k-1 之间的任何数字，并且总和为 <=k。可能性的总数可以由下式计算
sum(sum(1,y=0..k-x),x=0..k) = 1/2*k²+3/2*k+1
这应该能够解决大 k 的问题。
我对您问题中的“数字”有些困惑。数字组成索引，如 3 乘以 9 为 999。单元格 (999,888) 的数字总和为 51。如果您允许数字总和为 10^9，那么您可能有 10^8 位一个索引，产生大约 10^(10^8) 个条目，远远超出表格的正常大小。因此，我假设我的第一个解释。如果这不正确，那么您能再解释一下吗？
编辑：
好的，所以我的答案不会解决它。恐怕我没有看到一个好的公式或答案。我会将其视为着色/标记问题并标记所有有效单元格，然后使用其他一些技术来确保所有部分都已连接/计算它们。
我试图想出一些东西，但它太乱了。基本上我会尝试根据索引和k一次标记大部分。如果 k=20，您可以一次标记单元格范围 (0,0..299)（因为任何较低的索引将具有较低的索引总和）并继续检查范围的其余部分。我从 299 开始，将最后 2 个数字固定为其最大值，然后寻找第一个数字的最大值。然后对剩余的数百个 (300-999) 继续该过程，仅将最后一位固定为 300..389 和 390..398。但是，您已经可以看到它是一团糟......（尽管我想把它给你，你可能会得到一些更好的主意）
您可以立即看到的另一件事是您的问题在索引上是对称的，因此任何有效的单元格 (x,y) 都会告诉您还有另一个有效的单元格 (y,x)。在标记方案/dfs/bfs 中可以利用这一点。
于 2012-12-16T22:28:01.347 回答