思路: dp
分析:1 又是一道看了题解还不懂怎么个回事的题，然后各种YY之后有点感觉
2 题目要求的是在n个数中间插入n-1个的+或-使得结果能否被k整除
3 看一个数学的公式(a+b)%k = a%k+b%k，按照网上的题解dp[i][j]表示的是前i个数运算能否得到模为j，如果可以则dp[i][j] = true，否则为false
4 那么如果dp[i-1][j] = true，则可以知道dp[i][(j+arr[i])%k]] = true , dp[i][(j-arr[i])%k]] = true。怎么理解这个状态转移方程呢，因为对于arr[i]这个数我们可以加也可以减，所以说有两种的情况
5 由于题目要求的是模，所以我们只要把所有的负数全部搞成正数即可。
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAX = 110;
const int MAXN = 10010;
int n , k;
bool dp[MAXN][MAX];
int main(){
int num;
while(scanf("%d%d" , &n , &k) != EOF){
memset(dp , false , sizeof(dp));
scanf("%d" , &num);
dp[0][abs(num)%k] = true;
for(int i = 1 ; i < n ; i++){
scanf("%d" , &num);
num = abs(num)%k;
for(int j = 0 ; j < k ; j++){
if(dp[(i-1)%2][j]){
dp[i%2][(j+num)%k] = true;
dp[i%2][(j-num+k)%k] = true;
}
}
}
if(dp[(n-1)%2][0])
puts("Divisible");
else
puts("Not divisible");
}
return 0;
}
