[UVa] 10036 - Divisibility

題目網址: http://goo.gl/SOLc0D

題意:給一長度為 n 的數列與一數 k，問在數列的相鄰兩數之間插入 '+' 或 '-' ，是否存在一運算法使得整個運算結果能夠被 k 整除。(1 <= n <= 10000, 2 <= k <= 100)



解法:由於 (a+b)%k = (a%k)+(b%k) ，所以運算後的結果只會介於 0 ~ k-1 ，用DP可以考慮所有的情況，複雜度O(n*k)。

遞迴方程 dp[i][v] =
          { true, i = 0 and v = 0
          { false, i = 0 and 0 < v < k
          { dp[i-1][(v-num[i])%k] || dp[i-1][(v+num[i])%k], i > 0 and 0 <= v <= k-1
表示 當考慮第 i 個數字後，mod k之後的值是否可能為v

TAG: DP

注意:

程式碼:

	/**
	* Tittle: 10036 - Divisibility
	* Author: Cheng-Shih, Wong
	* Date: 2015/03/09
	* File: 10036 - Divisibility.cpp - solve it
	*/
	// include files
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	#define N 105
	#define P(x) ((x-1)&1)
	#define C(x) (x&1)
	// declarations
	int t;
	int n, k;
	int seq[10005];
	bool dp[2][N];
	// functions
	// main function
	int main( void )
	{
	// input
	scanf( "%d", &t );
	while( t-- ) {
	scanf( "%d%d", &n, &k );
	FOR( i, 1, n ) scanf( "%d", &seq[i] );
	// solve
	clr( dp, false );
	dp[0][0] = true;
	FOR( i, 1, n ) {
	clr( dp[C(i)], false );
	FOR( j, 0, k-1 ) if( dp[P(i)][j] ) {
	dp[C(i)][((j+seq[i])%k+k)%k] = true;
	dp[C(i)][((j-seq[i])%k+k)%k] = true;
	}
	}
	// output
	if( dp[C(n)][0] ) puts("Divisible");
	else puts("Not divisible");
	}
	return 0;
	}

view raw 10036 - Divisibility.cpp hosted with ❤ by GitHub