百練/北京大学2016年大学院入学試験（校外）E：Divisibility（ダイナミック企画）

タイトルのソース:http://poj.org/problem?id=1745
Divisibility
Time Limit: 1000 MS
メモリLimit: 100000 K
Description
Consider an arbitrary sequence of integers.Onese place+or-operators between integers in the sequence，thus derigdifferent arthmetical-express to different values.Let.extrace，forextre，The 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 cal the sequence of integers divisible by K if+or-operators can beplacced between integers in the sequence in such way that recus value is visible byK.Inthe above example，the sequence+17 sible You are to write a program that will determine divisibility of sequence offtegers. 
Input
The first line of the input file contains twointegers、N and K（1<=N==10000、2<=K==100）separated by aspace. The second line contains a sequence of N integers separated by spaces.Eachinter is not greater than 10000 by it's absolue. 
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.
Sample Input

4 7
17 5 -21 15

SampleOutput

Divisible

ソurce
Northeastern Europe 1999
------------------------------------------
問題を解く構想
ダイナミック企画（0-1バックパック）
タイトル自体のピットはC/C++里-20%-7=-6で1ではなく、+7で正数になります。
注意すべきなのは、前に聞いたことがありますが、これまでにない「cin vs.scanf」int a[10001]vs.int*a=new int*[n]前者の速度が後者より遅いということです。
練習のデータが弱いので、後の書き方でも大丈夫です。poj上のデータは比較的に厳しいです。必ず固定サイズの配列を直接開けてこそ、動的に配列を割り当てられません。cinでもできますが、cinバージョンは797 ms、scanfバージョンは297 msで、500 msの差があります。怖いですね
血と涙の教訓：
1.テーマがデータの個数の上限を教えたら、直接上限によって固定サイズの配列を開けます。
2.標準入力ストリームから大量のデータを読み込む場合は、scanfでcinを使わないでください。
------------------------------------------
コード

//E:Divisibility
//     : 1000ms     : 65536kB
//  
//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. 
//
//You are to write a program that will determine divisibility of sequence of integers. 
//  
//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. 
//  
//Write to the output file the word "Divisible" if given sequence of integers is divisible by K or "Not divisible" if it's not.
//    
//4 7
//17 5 -21 15
//    
//Divisible

#include
#include
#include
using namespace std;

int main()
{
#ifndef ONLINE_JUDGE
	ifstream fin("tm201602E.txt");
	int n,k,i,j;
	fin >> n >> k;
	int *num = new int[n];
	for (i=0; i> num[i];
		num[i] %= k;
		if (num[i]<0)							//       
		{
			num[i] += k;
		}
	}
	int **dp = new int*[n];
	for (i=0; i> n >> k;
	int num[10001];        //        
	for (i=0; i> num[i]; //    cin   ，    scanf
		num[i] %= k;
		if (num[i]<0)
		{
			num[i] += k;
		}
	}
	int dp[10001][100] = {} ;
	// dynamic programming
	dp[0][num[0]] = 1;
	for (i=1; i