poj.1745.Divisibility
poj.1745.Divisibility
问题描述
给N个数字和一个K，把N个数字加加减减后得到的数字是否能整除K。
问题分析
0/1背包相关问题
公式
dp[j] = dp[(j - v[i]) % k] || dp[(j + v[i]) % k]
动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include <iostream>
#include <vector>
using namespace std;
bool isDivisibility(vector<int>& v, int n, int k)
{
vector<bool>* dp = new vector<bool>(k);
vector<bool>* dptemp = new vector<bool>(k);
(*dp)[0] = true;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < k; j++)
{
(*dptemp)[j] = (*dp)[((j - v[i]) % k + k) % k] || (*dp)[((j + v[i]) % k + k) % k];
}
vector<bool>* temp = dp;
dp = dptemp;
dptemp = temp;
}
return (*dp)[0];
}
int main()
{
int n, k;
cin >> n >> k;
vector<int> v(n);
for (int i = 0; i < n; i++)
{
cin >> v[i];
}
bool result = isDivisibility(v,n,k);
cout<< (result ? "Divisible" : "Not divisible")<<endl;
return 0;
}
|