POJ1745Divisibility(01背包思想)
2024-08-27 05:30:15
Divisibility
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 11151 | Accepted: 3993 |
Description
Consider an arbitrary sequence of integers. One can place + or - operators between integers in the sequence, thus deriving different arithmetical expressions that evaluate to different values. Let us, for example, take the sequence: 17, 5, -21, 15. There are eight possible expressions: 17 + 5 + -21 + 15 = 16
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.
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 first line of the input file contains two
integers, N and K (1 <= N <= 10000, 2 <= K <= 100) separated by a
space.
The second line contains a sequence of N integers separated by
spaces. Each integer is not greater than 10000 by it's absolute value.
integers, N and K (1 <= N <= 10000, 2 <= K <= 100) separated by a
space.
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
Write to the output file the word "Divisible" if given
sequence of integers is divisible by K or "Not divisible" if it's not.
sequence of integers is divisible by K or "Not divisible" if it's not.
Sample Input
4 7
17 5 -21 15
Sample Output
Divisible
题意:输入n个数,通过添加+和-能否是的结果对k取余为0
思路:智商再次背碾压
首先一个数,不用说,第一个数之前不用加符号就是本身,那么本身直接对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>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[ + ][ + ],a[ + ];
int n,k;
int mod(int x)
{
if(x < )
{
return x + k;
}
else
return x;
}
int main()
{
while(scanf("%d%d", &n, &k) != EOF)
{
for(int i = ; i <= n; i++)
scanf("%d", &a[i]);
memset(dp, , sizeof(dp));
dp[][ mod(a[] % k) ] = ;
for(int i = ; i <= n; i++)
{
for(int j = ; j <= k; j++)
{
if(dp[i - ][j])
{
dp[i][ mod((j + a[i]) % k)] = ;
dp[i][ mod((j - a[i]) % k)] = ;
}
}
}
if(dp[n][])
printf("Divisible\n");
else
printf("Not divisible\n");
} return ;
}
最新文章
- lecture13-BP算法的讨论和置信网
- ES6 变量的解构赋值
- php继承与重载
- python 中对list做减法操作
- VisualStudio2013内置SQLServer入门(二)--增删改查
- java一点东西(3)
- 用angularjs开发下一代web应用(二):angularjs应用骨架(二)
- Java 7如何操纵文件属性
- CJOJ 2484 函数最小值 / Luogu 2085 函数最小值(STL优先队列,堆)
- Linux Debugging(六): 动态库注入、ltrace、strace、Valgrind
- HBase Master启动过程
- my.ini的路径分隔符
- RabbitMQ持久化
- How to SHA1 on macOS
- luogu1919 A*BProblem升级版 (FFT)
- (第十二周)final预发布视频
- log4j2笔记 #01# Architecture
- ios 数组和字典
- ApiGen 4.0配置项
- 【three.js练习程序】创建地球贴图