牛客小白月赛88 D 我不是大富翁

本文主要是介绍牛客小白月赛88 D 我不是大富翁，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：D-我不是大富翁

题目大意：圆形的圆盘被分为n个区域，当前在1号区域，给长度为m的数组，每次可以向前走或者向后走，必须走完数组的所有值，问结束能不能回到起点。

思路：dp，dp数组2个维度，第一维记录走的次数，第二维记录当前的位置。二重循环，第一重循环枚举走的次数，第二重循环枚举位置，n和m最大5000，不会超过时限。因为5000*5000的空间要求很大，而且本题的dp数组只记录是否到达可以使用bool开数组，节省空间。int也可以，longlong不行。

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N=1e6+10;
bool dp[5010][5010];
ll p[N];
int main()
{ios::sync_with_stdio(0),cout.tie(0),cin.tie(0);ll n,m;cin>>n>>m;for(int i=1;i<=m;i++){cin>>p[i];p[i]%=n;}dp[0][0]=1;for(int i=1;i<=m;i++){for(int j=0;j<n;j++){if(dp[i-1][(j-p[i]+n)%n]||dp[i-1][(j+p[i])%n])//如果之前可以到达{dp[i][j]=1;}}}if(dp[m][0])cout<<"YES";else cout<<"NO";return 0;
}

这篇关于牛客小白月赛88 D 我不是大富翁的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---