【洛谷】P1057传球游戏

【洛谷】P1057传球游戏

1.题意

见链接

2.分析

这题需要使用手动简单的模拟一下，原题中的一个测试用例便是一个好的例子，传球只能往左边或右边传，相应的，传球次数减一，我们深搜这个状态直到最终传到第一个人手里。于是得到深搜的主要过程：
f[i][j] = dfs( (i+1)%n,j-1 ) + dfs( (i-1 + n)%n,j-1 );。其中f[i][j]代表的是经过j次传球回到i号人手中

3.代码

第一次提交的代码如下：

#include<iostream>
#include<cstdio>
using namespace std;const int maxN = 35;
int n,m;	
int f[maxN][maxN];//f[i][j] 用于计算"经过j次传球回到i号人手中" //计算"经过j次传球回到i号人手中" 
int dfs(int i,int j){	//我也是因为“根据是否是0决定是否返回“导致TLE.if(f[i][j] != -1)return f[i][j];if(j == 0 && i!=0)return 0;	//printf("i = %d,j= %d\n",i,j);//计算值 //1.(i-1+n)%nf[i][j] = dfs( (i+1)%n,j-1 ) + dfs( (i-1 + n)%n,j-1 );		return f[i][j];		
}int main(){	scanf("%d%d",&n,&m);fill(f[0],f[0]+maxN*maxN,-1);f[0][0] = 1;//球本来就在1号手中 	dfs(0,m);printf("%d\n",f[0][m]); 
}

执行结果如下：
看到这样的提交结果，大概能猜到具体的问题。（大概率是程序出现了问题，而不是测试用例导致的超时。因为后面两个测试用例都没有超时，而且我在深搜里用的是记忆化搜索，理应不会出现这种问题。）
我手贱下载了一下未过的测试用例，如下：

输入：
10 29
0输出：
0

根据上面的问题分析（是程序导致死循环而不是测试用例），那么就应该查看是否是深搜的过程中没有及时返回（因为只有不能返回才会导致死循环）。那么是什么地方会出现无法返回呢？ 。看dfs()中的代码：

//计算"经过j次传球回到i号人手中" 
int dfs(int i,int j){	if(f[i][j] != 0)return f[i][j];if(j == 0 && i!=0)return 0;//计算值 //1.(i-1+n)%nf[i][j] = dfs( (i+1)%n,j-1 ) + dfs( (i-1 + n)%n,j-1 );		return f[i][j];		
}

其中的返回语句只有两句：

if(f[i][j] != 0)return f[i][j];
if(j == 0 && i!=0)return 0;

很清楚，可以看到这里有一个自相矛盾的地方。第二个if的返回值是0（表明该次深搜过程的f[i][j]已经计算好了），但是第一个if却是根据f[i][j]!=0来返回，这就导致上一次计算好的，这次还是会计算递归计算，从而导致死循环。

将f[i][j]初始化为-1，然后再根据是否是-1进行返回，就可以顺利得出答案了。AC代码如下：

#include<iostream>
#include<cstdio>
using namespace std;const int maxN = 35;
int n,m;	
int f[maxN][maxN];//f[i][j] 用于计算"经过j次传球回到i号人手中" //计算"经过j次传球回到i号人手中" 
int dfs(int i,int j){			if(f[i][j] != -1)return f[i][j];if(j == 0 && i!=0)return 0;			//计算值 //1.(i-1+n)%nf[i][j] = dfs( (i+1)%n,j-1 ) + dfs( (i-1 + n)%n,j-1 );		return f[i][j];		
}int main(){	scanf("%d%d",&n,&m);fill(f[0],f[0]+maxN*maxN,-1);f[0][0] = 1;//球本来就在1号手中 	dfs(0,m);printf("%d\n",f[0][m]); 
}

4.测试用例

4 1
0