ダイナミック企画：ZOJ 2042_Divisibility

【回る】http://fuliang.iteye.com/blog/143188
 
質問：Consinder an arbitrary sequence of integers.One can place+or-operators between integers in the sequence，thus dering different arthmetical expressis to different values.Lext，forextre，The 5  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 cal the sequence of integers divisible by K if+or-operators can be placed between integers in the sequence in such way that reulting value is divisible byK.Inthe above example，the sequence+7but is not divisible by 5.You are to write a program that will determine divisibility of sequence of integers.Input The e e e e multiple test cases，the first line is the number of test cases.The first iness inessseparated by space s.The second line contains a sequence of N integers separated by spaces.Each integer is not greater than 10000 by it's absoute value.Output Write to the output file the world“Divieble”if it's not.Sample Input 2 4 17-21 15 4 5-21 15 Sample Output Divisible Not divisibleというテーマは所与の山の数の中に+-号を入れて、所与のKを割り切れるかどうかを判断します。この問題はまず人に与える感じが貧しい/検索ですが、10000個以内であれば、最悪です。計算された時間はかなり長いです。指数レベルの複雑さを多項式レベルに変えて動的な計画を考えることができます。この問題の動的な計画情報は非常に隠しています。これらの数の演算を直接サブ問題に分類すると、これらのサブ問題は繰り返しません。サブ問題の最適解を記憶することによって、繰り返し計算を避けることができます。しかし、この問題をよく分析してみると、表現の値を本当に求める必要がないことが分かりました。私たちはステップごとに計算した結果のKの余りを覚えておけばいいです。このように計算した結果は0～Kの間にあります。この計算過程をツリー構造と表現すれば               a 1         /           \       a 1-a 2          a 1+a 2      /  \          /      \ a 1-a 2-a 3 a 1-a 2+a 3 a 1+a 2-a 3 a 1+a 2+a 3……………というように、第j層は2^j個の計算結果がありますが、もし私達が計算するたびにKに対してモデルを求めたら、この2^j個の値は全部0~k-1の間にあります。もし1層の中の2つのノードの値が同じで保存されたら、第1個のノードの値は明らかに計算できます。また、このような同じ値が直接検索できます。実際にこのように重複するノード計算はかなり多いです。（指数レベル2^jの数は定数0〜kの範囲です。）このようにして、ツリーの幅を1〜kの範囲に制限しました。高さはNです。複雑度は多項式レベルO（k＊N）になりました。コードは以下の通りです。

package com.iteye.caoruntao.zoj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author caoruntao
 *
 */
public class ZOJ2042_Divisibility {

	private static int N;
	private static int K;
	private static int[][] flag = new int[10005][105];
	private static int[] a = new int[10005];
	
	public static int compute(int level, int value){
		if(flag[level][value] != -1){
			return flag[level][value];
		}
		int check;
		int t1 = (value + a[level]) % K;
		int t2 = (value - a[level]) % K;
		t1 = t1 < 0 ? t1 + K : t1;
		t2 = t2 < 0 ? t2 + K : t2;
		
		if(level == N){
			if(value%K == 0){
				check = 1;
			}else{
				check = 0;
			}
		}
		else if(compute(level+1, t1) == 1){
			check = 1;
		}
		else if(compute(level+1, t2) == 1){
			check = 1;
		}
		else{
			check = 0;
		}
		return flag[level][value]=check;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int n;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = "";
		String result = "";
		try {
			str = br.readLine();
			n = Integer.parseInt(str);
			for(int i=0; i<n; i++){
				str = br.readLine();
				String[] strArr = str.split(" ");
				N = Integer.parseInt(strArr[0]);
				K = Integer.parseInt(strArr[1]);
				str = br.readLine();
				strArr = str.split(" ");
				for(int j=0; j<N; j++){
					a[j] = Integer.parseInt(strArr[j]);
				}
				
				for(int j=0; j<=N; j++){
					for(int m=0; m<=K; m++){
						flag[j][m] = -1;
					}
				}
				result = compute(1, a[0]%K)==1 ? "Divisible" : "Not divisible";
				System.out.println(result);
			}
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}

}