C题过96.67%,求助

这样的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';
}

全部评论
建议第一维度至少压成2个维度,因为当前 dp[((j-a[i])%n+n)%n] &nbs***bsp;dp[((j+a[i])%n+n)%n] 的枚举顺序可能早于 dp[j]
1
送花
回复
分享
发布于 03-08 21:29 江苏

相关推荐

1 收藏 评论
分享
牛客网
牛客企业服务