zoj 2042 - Divisibility
來源：程序員人生 發布時間：2014-10-17 06:44:15 閱讀次數：2789次
題目：給你一串數字，不改變數字的順序而在他們之間加入減號或者加號，問結能否整除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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
