小白月赛D我不是大富翁
我不是大富翁
https://ac.nowcoder.com/acm/contest/75771/D
一个dp问题
dp[i][j]表示从第i次可以到达距离为j的位置（dp[i][j] = 1）
如果dp[i-1][j] = 1,就从这个位置计算下一次可能到的位置
最后判断dp[m][0]是否为1，注意dp[m][0]表示m次仍在1号位置（j代表着相对位移）
#include<bits/stdc++.h>
#define int long long
typedef long long ll;
using namespace std;
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
void solve(){
int n,m;
cin>>n>>m;
int a[5050],dp[5050][5050];
for (int i = 1; i <= m; ++i) {
cin>>a[i];
a[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] == 1) {
dp[i][(j + a[i]) % n] = 1;
dp[i][(j + n - a[i]) % n] = 1;
}
}
}
if(dp[m][0] == 1){
cout<<"YES"<<endl;
} else{
cout<<"NO"<<endl;
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(NULL),cout.tie(NULL);
int t = 1;
//cin>>t;
while(t--){
solve();//1 2 3 4 5
}
return 0 ;
}
