本文主要是介绍深信服 抓兔子，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
3 2
2 2
yes
第一反应是枚举兔子起点+DFS，不过同学说过不了。
dp的思路是：第i天第j个洞是否可能存在兔子，当天被访问的洞标位0，其余能到的洞为1，最后一天如果全是0的就一定能捉到
dp[i][j]==1 ==> dp[i+1][j-1]=1 dp[i+1][j+1]=1（需特判边界）
且可以优化至一维滚动数组（懒，用的二维）
#include <iostream>
using namespace std;
int n,k;
int dp[1002][1001];
int visit[1001];
int main(){cin>>n>>k;int i;for(i=0;i<k;i++){cin>>visit[i];}memset(dp,0,sizeof(dp));for( i=0;i<n;i++){dp[0][i]=1;}//初始化第一天兔子可能在任一个洞，值为1；dp[0][visit[0]-1]=0;//0代表兔子第1天不在j洞for(i=0;i<k;i++){for(int j=0;j<n;j++){if(dp[i][j]==1){if(j==0){dp[i+1][j+1]=1;}else if(j==n-1){dp[i+1][j-1]=1;}else{dp[i+1][j-1]=1;//这里是所以可能的情况dp[i+1][j+1]=1;}}dp[i+1][visit[i+1]-1]=0;//0代表兔子第i天不在j洞}}int flag=1;for(i=0;i<n;i++){if(dp[k][i]==1){//最后一天全等于0代表兔子无处可藏flag=0;break;}}if(flag){puts("yes");}else{puts("no");}return 0;
}
从所以可能的结果中看是否有我们要的结果
这篇关于深信服 抓兔子的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
