讨论 / 我吐死,这题需要高精度啊
文修 2013-10-16 08:08:00
点我顶贴 收藏 删除
居然。。。被它气得半死,想了很久,只通过六组数据,四组超界。。。唉,去学高精度啰。。。
#1 Zx.MYS@2008-10-23 07:02:00
回复 删除
没有吧?
#2 飞雪天涯@2008-10-23 08:57:00
回复 删除
No need of High Precision

#include<fstream>

#include<iostream>

//#define debug

#define maxn 20

#define maxm 20

using namespace std;

#define fin cin

#define fout cout

//ifstream fin ("NOIPC4.in");

//ofstream fout ("NOIPC4.out");

#ifdef debug

ofstream deb ("debug.log");

#endif

bool chessboard[maxn+1][maxm+1]={true};

long long blank[maxn+1][maxm+1]={0};

int n,m,x,y;

bool isok(int a,int b){

if (a>=0&&a<=n&&b>=0&&b<=m) return true;

return false;

}

void input_init(){

fin>>n>>m>>x>>y;

memset(chessboard,true,sizeof(chessboard));

memset(blank,0,sizeof(blank));

if (isok(x,y))chessboard[x][y]=false;

if (isok(x-1,y+2))chessboard[x-1][y+2]=false;

if (isok(x-2,y+1))chessboard[x-2][y+1]=false;

if (isok(x-2,y-1))chessboard[x-2][y-1]=false;

if (isok(x-1,y-2))chessboard[x-1][y-2]=false;

if (isok(x+1,y-2))chessboard[x+1][y-2]=false;

if (isok(x+2,y-1))chessboard[x+2][y-1]=false;

if (isok(x+2,y+1))chessboard[x+2][y+1]=false;

if (isok(x+1,y+2))chessboard[x+1][y+2]=false;

if (chessboard[0][0]) blank[0][0]=1;

else blank[0][0]=0;

for (int i=1;i<=n;i++)

if (chessboard[i][0])

blank[i][0]=blank[i-1][0];

else blank[i][0]=0;

for (int j=1;j<=m;j++)

if (chessboard[0][j])

blank[0][j]=blank[0][j-1];

else blank[0][j]=0;

}

void work(){

for (int i=1;i<=n;i++)

for (int j=1;j<=m;j++)

{

if (chessboard[i][j])

blank[i][j]=blank[i-1][j]+blank[i][j-1];

else blank[i][j]=0;

}

#ifdef debug

deb<<’\t’;

for (int j=0;j<=n;j++)

deb<<j<<’\t’;

deb<<endl;

for (int i=0;i<=n;i++){

deb<<i<<’\t’;

for (int j=0;j<=m;j++)

deb<<blank[i][j]<<’\t’;

deb<<endl;

}

#endif

}

void output(){

fout<<blank[n][m];

}

int main(void){

input_init();

work();

output();

// while(1);

return 0;

}

#3 xiaokeke@2008-10-23 15:51:00
回复 删除
int64就可以了。

我的pascal和ls的代码惊人的相似呢……

#4 wish@2008-10-23 21:18:00
回复 删除
2F:代码写的这么丑就不要在这里现世了,你已经不是一次两次了

program p69(input, output);

var

 n, m, x, y, i, j: longint;

 map: array [-10..30, -10..30] of boolean;

 dp: array [-1..20, -1..20] of int64;

begin

 fillchar(map, sizeof(map), 0);

 fillchar(dp, sizeof(dp), 0);

 readln(n, m, x, y);

 map[x, y] := true;

 map[x - 2, y - 1] := true;

 map[x - 1, y - 2] := true;

 map[x - 2, y + 1] := true;

 map[x - 1, y + 2] := true;

 map[x + 1, y + 2] := true;

 map[x + 2, y + 1] := true;

 map[x + 1, y - 2] := true;

 map[x + 2, y - 1] := true;

 dp[-1, 0] := 1;

 for i := 0 to n do

  for j := 0 to m do

   if not map[i, j] then

    dp[i, j] := dp[i - 1, j] + dp[i, j - 1];

 writeln(dp[n, m])

end.

#5 我是天才他哥@2008-10-23 21:22:00
回复 删除
DP。。。怎么会是高精度
#6 hades@2008-10-23 21:43:00
回复 删除
qword 就可以

#7 ply_py@2010-11-27 19:02:00
回复 删除
看到2L的代码我大笑而过...

#include <iostream>

#include <math.h>

using namespace std;

int n, m, x, y;

long long map[21][21];

bool safe(int a, int b)

{

return !((abs(a-x)*abs(b-y)==2) || (a==x && b == y));

}

int main()

{

cin >> n >> m >> x >> y;

map[0][0] = 1;

for (int i = 1; safe(i,0) && i<=n; i++)

map[i][0] = map[i-1][0];

for (int i = 1; safe(0,i) && i<=m; i++)

map[0][i] = map[0][i-1];

for (int i = 1; i <= n; i++)

for (int j = 1; j <= m; j++)

if (safe(i,j))

map[i][j] = map[i-1][j]+map[i][j-1];

cout << map[n][m];

return 0;

}

#8 朝雨@2011-01-04 02:08:00
回复 删除
DP+int64
#9 goon@2011-08-16 22:20:00
回复 删除
好吧我错了,原来要开Int64
#10 goon@2011-08-16 22:22:00
回复 删除
编译竟然超过6S于是WA 0了
查看更多回复
提交回复