题目大意:给出N和K,然后给出N个整数(不论正负),问在这N个数中,每两个数之间(即N - 1个位置)添加加号或者减号,然后运算的值对K取余,如果余数等于0输出Divisible,否则输出Not divisible
解题思路:
拿
4 7
17 5 -21 15
举例
首先一个数,不用说,第一个数之前不用加符号就是本身,那么本身直接对K取余,
那么取17的时候有个余数为2
然后来了一个5,
(2 + 5)对7取余为0
(2 - 5)对7取余为4(将取余的负数变正)
那么前2个数有余数0和4
再来一个-21
(0+21)对7取余为0
(0-21)对7取余为0
(4+21)对7取余为4
(4-21)对7取余为4
再来一个-15同样是这样
(0+15)%7 = 1
(0-15)%7 = 6
(4+15)%7 = 5
(4-15)%7 = 3
同理可以找到规律,定义dp[i][j]为前i个数进来余数等于j是不是成立,1为成立,0为不成立
那么如果dp[N][0]为1那么即可以组成一个数对K取余为0
初始化dp为0
然后dp[1][a[1]%k] = 1
for i = 2 to N do
for j = 0 to K do
if(dp[i - 1][j])
dp[i][(j + a[i])%k] = 1;
dp[i][(j - a[i])%k] = 1;
if end
for end
for end
#include <iostream> using namespace std; #define MAXN 10001 int dp[MAXN][101]; int posmod(int n,int k){ 正数取余 n = n % k; while(n < 0) n+=k; return n; } int main(){ int n,k; int i ,j ,tmp; int a[MAXN]; while(cin>>n>>k){ memset(dp,0,sizeof(dp)); for(i = 1;i <= n;i++) cin>>a[i]; dp[1][posmod(a[1],k)] = 1; for(i = 2;i <= n;i++){ for(j = 0;j < k;j++){ if(dp[i - 1][j]){ dp[i][posmod(j + a[i],k)] = 1; dp[i][posmod(j - a[i],k)] = 1; } } } if(dp[n][0]){ cout<<"Divisible"<<endl; }else{ cout<<"Not divisible"<<endl; } } return 0; }