这样的DP是否存在遗漏?
void solve() { int n,m; cin>>n>>m; vector<int> a(m+1); for(int i=1;i<=m;i++){ cin>>a[i]; a[i]=((a[i]%n)+n)%n; } vector<int> dp(n,-1); dp[0]=0; for(int i=1;i<=m;i++){ for(int j=0;j<n;j++){ if(dp[((j-a[i])%n+n)%n]==i-1) {dp[j]=i;} if(dp[((j+a[i])%n+n)%n]==i-1) {dp[j]=i;} } } cout<<(dp[0]==m?"YES":"NO")<<'\n'; }
全部评论
(1) 回帖