请教：iheart上提供的pdf格式的胖子能用吗？# PennySaver - 省钱一族
R*i
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];
}
}
}
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
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];
}
}
}
