指针原来是套娃的


私信TA

用户名:uq_92467646842

访问量:18701

签 名:

数学改变科学,科学改变世界

等  级
排  名 11
经  验 21312
参赛次数 49
文章发表 119
年  龄 0
在职情况 学生
学  校
专  业 物联网工程

  自我简介:

QQ:2830671713

解题思路:

先来说一下题意,n个数,每个数前面随意加上+-号(当然+号等于没加),然后所有的数相加,判断和是否为k的整数。
两种方法,一个是使用dfs深搜,将每种情况都进行尝试,时间复杂度2^n,能过本网站数据,数据量大的时候会超时。

还有一种是dp,这是最好的方法。

dfs代码:

#include <bits/stdc++.h>

using namespace std;

int p[10007];
int n,m,vis=0;

void dfs(int k) {
	if(k==n) {//全部更改过位置 
		int z=0;
		for(int i=0; i<n; i++) {
			z+=p[i];
		}
		if(z%m==0)vis=1;//如果可以整除
		return; 
		
	} else {
		for(int i=0; i<2; i++) {
			if(i&1) {
				dfs(k+1);
			} else {
				p[k]*=-1;
				dfs(k+1);
				p[k]*=-1;
			}
		}
	}

}

int main () {

	cin>>n>>m;
	for(int i=0; i<n; i++) {
		cin>>p[i];
	}
	dfs(0);
	cout<<(vis?"YES":"NO"); 

	return 0;
}


来详细说一下dp代码,dp[i][j]为前i个数是否可以被j整除,1表示可以,0不可以。

因为最后所有的值是要相加在一起的,所以最后的值依赖于前面的情况。

以第二个数为例,如果想要第一个数加上第二个数后sum对k取余值为j,那么第一个数p1只有两种情况,一个是p1==j-a2,一个是p1==j+a2(这里对p2前加(-)号)

推广到所有的数身上,想要加到第i个数sum%k的值为j,那么加到第i-1个数时必须满足两种情况(j-pi或者j+pi)中的一个,这样在加上第i个数或减去第i个数后和sum才为j,j%k=j(j<k)。

根据(a+b)%k=(a%k+b%k)%k,可以先进行取余后处理,一方面可以减少数组开销另一方面确保j<k。

这样我们就可以写递推式了,dp[i][j]代表的是前i个数是否可以被j整除,dp[i][j]就和(dp[i-1][(j+p[i])%k]、dp[i-1][(j-p[i])%k])有关了,只有这两个中的一个为真,dp[i][j]才为真。

递推式:dp[i][j]=dp[i-1][(j+p[i]+k)%k] || dp[i-1][(j-p[i]+k)%k]

两个做或运算,有真则真,注意这里分别+k,是为了防止j-p[i]为数组下标为负数的情况。

根据同余 (j-p[i]+k)%k=(j-p[i])%k+k%k=(j-p[i])%k


dp代码:

#include <bits/stdc++.h>

using namespace std;

int p[10007];
bool dp[10007][107];
int n,k;

int main () {

	cin>>n>>k;
	for(int i=1; i<=n; i++) {
		cin>>p[i];
		p[i]%=k;
	}
	dp[0][0]=1;//边界,记为1
	for(int i=1; i<=n; i++) {
		for(int j=0; j<k; j++) {
			dp[i][j]=dp[i-1][(j+p[i]+k)%k]||dp[i-1][(j-p[i]+k)%k];
		}
	}
	cout<<(dp[n][0]?"YES":"NO");//dp[n][0]表示前n个数相加,对k取余余数为0,即:前n个数相加有可以整除k的情况

	return 0;
}

dp的核心是dp[i][j]为前i个数是否可以被j整除,这是本题的核心。

以上。

 

0.0分

1 人评分

  评论区