zoj 2042 - Divisibility
来源：程序员人生 发布时间：2014-10-17 06:44:15 阅读次数：2648次
题目：给你一串数字，不改变数字的顺序而在他们之间加入减号或者加号，问结能否整除m。
分析：dp，背包类似物。容量为0 ~ m-1。
状态：f（i，j）为前i个数组合结果的余数为j的真值；
转移：f（i，j）= max（f（i-1，j-a[i]），f（i-1），j+a[i]）{ 结果对应值在0 ~ m-1之间 }；
说明：（2011-9-19 11:24）。
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <stdio.h>
using namespace std;
bool F[ 10003 ][ 103 ];
int N[ 10003 ];
int main()
{
int t,n,k;
while ( scanf("%d",&t) != EOF )
while ( t -- ) {
scanf("%d%d",&n,&k);
for ( int i = 0 ; i < n ; ++ i )
scanf("%d",&N[ i ]);
for ( int i = 0 ; i < n ; ++ i )
N[ i ] = (k+N[ i ]%k)%k;
memset( F, false, sizeof( F ) );
F[ 0 ][ N[ 0 ] ] = true;
for ( int i = 1 ; i < n ; ++ i )
for ( int j = 0 ; j < k ; ++ j )
if ( F[ i-1 ][ j ] ) {
F[ i ][ (k+j-N[ i ])%k ] = true;
F[ i ][ (k+j+N[ i ])%k ] = true;
}
if ( F[ n-1 ][ 0 ] )
printf("Divisible
");
else
printf("Not divisible
");
if ( t ) printf("
");
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
