R*****i
发帖数: 2126 | 1 CSDN上的编程挑战题。
http://hero.csdn.net/Question/Details?ID=610&ExamID=605
我的算法貌似不对，请问正确算法是神马？
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;
namespace GridWalk
{
class Program
{
static void Main(string[] args)
{
List nlist = new List();
string line = Console.ReadLine();
while (!string.IsNullOrEmpty(line))
{
nlist.Add(int.Parse(line));
line = Console.ReadLine();
}
foreach (int n in nlist)
{
Console.WriteLine(GridWalk.GetPathNumber(n));
}
}
}
public class GridWalk
{
const int MAX_LEN = 1001;
private static BigInteger[] in_in_out_out = new BigInteger[MAX_LEN];
private static BigInteger[] in_out_in_out = new BigInteger[MAX_LEN];
private static BigInteger[] in_out_out_in = new BigInteger[MAX_LEN];
private static BigInteger[] out_out_in_in = new BigInteger[MAX_LEN];
private static BigInteger[] out_in_out_in = new BigInteger[MAX_LEN];
private static BigInteger[] out_in_in_out = new BigInteger[MAX_LEN];
public static BigInteger GetPathNumber(int num)
{
if (num == 1)
{
return 2;
}
else if (num >=2)
{
in_in_out_out[2] = 4;
in_out_in_out[2] = 4;
in_out_out_in[2] = 4;
out_out_in_in[2] = 4;
out_in_out_in[2] = 4;
out_in_in_out[2] = 4;
}
for (int cols = 3; cols <= num; cols++)
{
in_in_out_out[cols] = 0;
in_out_in_out[cols] = 0;
in_out_out_in[cols] = 0;
out_out_in_in[cols] = 0;
out_in_out_in[cols] = 0;
out_in_in_out[cols] = 0;
//1. in_in_out_out
in_out_out_in[cols] += in_in_out_out[cols - 1] * 2;
in_in_out_out[cols] += in_in_out_out[cols - 1] * 2;
in_out_in_out[cols] += in_in_out_out[cols - 1] * 2;
//2. in_out_in_out
in_in_out_out[cols] += in_out_in_out[cols - 1] * 2;
//3. in_out_out_in
in_out_out_in[cols] += in_out_out_in[cols - 1] * 2;
//4. out_out_in_in
out_out_in_in[cols] += out_out_in_in[cols - 1] * 2;
out_in_out_in[cols] += out_out_in_in[cols - 1] * 2;
in_out_out_in[cols] += out_out_in_in[cols - 1] * 2;
//5. out_in_out_in
out_out_in_in[cols] += out_in_out_in[cols - 1] * 2;
//6. out_in_in_out
out_in_in_out[cols] += out_in_in_out[cols - 1] * 2;
out_out_in_in[cols] += out_in_in_out[cols - 1] * 2;
in_in_out_out[cols] += out_in_in_out[cols - 1] * 2;
}
return in_in_out_out[num] + in_out_in_out[num] + in_out_out_in[
num]
+ out_out_in_in[num] + out_in_out_in[num] + out_in_in_out[
num];
}
}
} | h*******e
发帖数: 1377 | 2 记得是一种很复杂很复杂的dp。
我做出过不带对角线的哈密尔顿路条数，这个应该类似那道题。 | A*****i
发帖数: 3587 | | l*********8
发帖数: 4642 | 4 my 2 cents:
in[k]： k列棋盘时，从最后一列开始的哈密尔顿路的数目
inout[k]: k列棋盘时，从最后一列开始且回到最后一列的哈密尔顿路的数目
inout[0] = 1;
inout[1] = 2;
in[0] = 1;
in[1] = 2;
inout[k] = 2*inout[k-1];
in[k] = 2*in[k-1] + 2*inout[k-1] + 4*inout[k-2];
最终答案：
count[n] = 2*in[n] + sum(4*inout[i]*in[n-i-1] | 1<=i<=n-2)
【在 R*****i 的大作中提到】
: CSDN上的编程挑战题。
: http://hero.csdn.net/Question/Details?ID=610&ExamID=605
: 我的算法貌似不对，请问正确算法是神马？
: using System;
: using System.Collections.Generic;
: using System.Linq;
: using System.Text;
: using System.Numerics;
: namespace GridWalk
: {
| R*****i
发帖数: 2126 | 5 我的算法不知道究竟错在哪里. 题目只给出了1,2,3的答案, 所以无法验证我的算法.
我的算法是, 不在最外面的是里, 最外面的是外, 一共有6种case,
里-里-外-外
里-外-里-外
里-外-外-里
外-外-里-里
外-里-外-里
外-里-里-外
然后再添加一列的情况,
里-里-外-外 --> 里-里-外-外, 里-外-外-里, 里-外-里-外, 每一种都是2倍
里-外-里-外 --> 里-里-外-外, 2倍
里-外-外-里 --> 里-外-外-里, 2倍
外-外-里-里 --> 外-外-里-里, 外-里-外-里, 里-外-外-里, 每一种都是2倍
外-里-外-里 --> 外-外-里-里, 2倍
外-里-里-外 --> 外-里-里-外, 外-外-里-里, 里-里-外-外, 每一种都是2倍 | h*******e
发帖数: 1377 | 6 我做得是四行N列的~~~2行N列似乎不那么难，教你个方法，自己找错，自己写测试数据
， 1， 2， 3， 。。。10 的情况之后写个暴搜比对，之后你差不多就能发现错误的数
据了。然后带进去查找程序错误。
【在 R*****i 的大作中提到】
: 我的算法不知道究竟错在哪里. 题目只给出了1,2,3的答案, 所以无法验证我的算法.
: 我的算法是, 不在最外面的是里, 最外面的是外, 一共有6种case,
: 里-里-外-外
: 里-外-里-外
: 里-外-外-里
: 外-外-里-里
: 外-里-外-里
: 外-里-里-外
: 然后再添加一列的情况,
: 里-里-外-外 --> 里-里-外-外, 里-外-外-里, 里-外-里-外, 每一种都是2倍
| R*****i
发帖数: 2126 | 7 谢谢楼上的建议, 刚试了一下暴搜, 4列的时候我的算法结果也是对的, 是416. | l*********8
发帖数: 4642 | 8 难道你没有mod (10^9 + 7)
【在 R*****i 的大作中提到】
: 谢谢楼上的建议, 刚试了一下暴搜, 4列的时候我的算法结果也是对的, 是416.
| R*****i
发帖数: 2126 | 9
噢, 没看懂那是啥意思, 直接输出大数了.
【在 l*********8 的大作中提到】
: 难道你没有mod (10^9 + 7)
| R*****i
发帖数: 2126 | 10
靠, 还真是的. 妈乐个八字, 我TM当时就没看明白最后一句.
【在 l*********8 的大作中提到】
: 难道你没有mod (10^9 + 7)
| l*********8
发帖数: 4642 | 11 刚才测试了一下，我的算法也是正确的。
贴个小数据版的程序（没加mod）
int solveSmall(int n) {
if (n < 1) return 0;
vector in(n+1), inout(n+1);
inout[0] = 1, inout[1] = 2;
in[0] = 1, in[1] = 2;
for (int k=2; k<=n; ++k) {
inout[k] = 2 * inout[k-1];
in[k] = inout[k] + 2 * in[k-1] + 4 * in[k-2];
}
int count = min(2, n) * in[n];
for (int i=1; i<=n-2; ++i)
count += 4 * inout[i] * in[n-i-1];
return count;
} | M*******a
发帖数: 1633 | |
|
