首页 > 代码库 > poj 1745 Divisibility(DP + 数学)
poj 1745 Divisibility(DP + 数学)
题目链接:http://poj.org/problem?id=1745
Description
17 + 5 + -21 - 15 = -14
17 + 5 - -21 + 15 = 58
17 + 5 - -21 - 15 = 28
17 - 5 + -21 + 15 = 6
17 - 5 + -21 - 15 = -24
17 - 5 - -21 + 15 = 48
17 - 5 - -21 - 15 = 18
We call the sequence of integers divisible by K if + or - operators can be placed between integers in the sequence in such way that resulting value is divisible by K. In the above example, the sequence is divisible by 7 (17+5+-21-15=-14) but is not divisible by 5.
You are to write a program that will determine divisibility of sequence of integers.
Input
The second line contains a sequence of N integers separated by spaces. Each integer is not greater than 10000 by it‘s absolute value.
Output
Sample Input
4 7 17 5 -21 15
Sample Output
Divisible
Source
题意:
给出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
以上系转载:http://blog.csdn.net/wangjian8006/article/details/10170671
代码如下:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int a[10017]; int dp[10017][117]; //dp[i][j]为前i个数进来余数等于j是不是成立,1为成立,0为不成立 int n, k; int f(int tt) { tt %= k; while(tt < 0) tt+=k; return tt; } int main() { while(~scanf("%d %d",&n,&k)) { memset(dp,0,sizeof(dp)); for(int i = 1; i <= n; i++) { scanf("%d",&a[i]); } dp[1][f(a[1])] = 1; for(int i = 2; i <= n; i++) { for(int j = 0; j < k; j++) { if(dp[i-1][j]) { dp[i][f(j+a[i])] = 1; dp[i][f(j-a[i])] = 1; } } } if(dp[n][0]) { printf("Divisible\n"); } else printf("Not divisible\n"); } return 0; }
poj 1745 Divisibility(DP + 数学)