题目链接：http://poj.org/problem?id=1745
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 13431 | Accepted: 4774 |
Description
Input
Output
Sample Input
4 7 17 5 -21 15
Sample Output
Divisible
Source
题目大意：给N个数字和一个K，把N个数字加加减减后得到的数字是否能整除K。
大概思路：
一、暴力，全排列，爆炸，out！
二、0/1背包
状态：bool dp[ i ][ x ], 长度为 i 的序列的加减结果模 K 的后的 X 为真或为假
状态转移： dp[ i+1 ][ (((x-num [i+1])%K)+K)%K ] = dp[ i ][ x ] 减第 i+1 个数
dp[ i+1 ][ (((x+num [i+1])%K)+K)%K ] = dp[ i ][ x ] 加第 i+1 个数
AC code （1224k 360ms)：
1 ///POJ 1745 【0/1背包】 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #include <algorithm> 6 #define INF 0x3f3f3f3f 7 using namespace std; 8 9 const int MAXN = 1e4+10; 10 const int MAXK = 111; 11 12 int num[MAXN]; 13 bool dp[MAXN][MAXK]; 14 int N, K; 15 16 void slv() 17 { 18 memset(dp, 0, sizeof(dp)); 19 dp[1][((num[1]%K)+K)%K] = true; 20 for(int i = 1; i < N; i++) 21 { 22 for(int p = 0; p < K; p++) 23 { 24 if(dp[i][p]) 25 { 26 dp[i+1][(((p+num[i+1])%K)+K)%K] = true; 27 dp[i+1][(((p-num[i+1])%K)+K)%K] = true; 28 } 29 } 30 } 31 if(dp[N][0]) printf("Divisible\n"); 32 else printf("Not divisible\n"); 33 } 34 35 int main() 36 { 37 scanf("%d%d", &N, &K); 38 for(int i = 1; i <= N; i++) 39 { 40 scanf("%d", &num[i]); 41 } 42 slv(); 43 return 0; 44 }
原文：https://www.cnblogs.com/ymzjj/p/9380392.html