UVa10036 - Divisibility (動態規劃)

題目大意:

給你 n 個數字 與 x ，在 n 個數字中加上 - or + ， 判斷組合後的總合是否可以被 x 整除?

分析:

可能很多人會想排列組合，但會TLE

但是，想法其實只要在稍微思考一下就能想通了 (除非你太笨)

每一次在幫數字做 加減法後餘數儲存至二維陣列，狀態轉移即可 (是不是不難阿)

可寫成 DP 遞迴式， Dp[y + 1 , intNum[i] % x ]= DP[ y , intNum[i] ]

其中 y 為第 n 個數字， intNum 為 數字隊列。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL

using namespace std;
int intMap[10010][110] = {0} ;


int non_negative(int intNum , int K , int J){
    //debug
    //cout << intNum << ' ' ;

    intNum = (intNum + J ) % K ;
    while(intNum < 0)
        intNum += K ;
    return intNum % K ;
}


void print_map(int *intMap , int N , int K){
    for(int i = 0 ; i < N ; i++){
        for(int j = 0 ; j < K ; j++)
            cout << *(intMap + i + j) << ' ' ;
        cout << '\n' ;
    }
}


int main()
{
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin );
    freopen("out.txt" , "w" , stdout );
#endif // LOCAL
    int intCase , N , K ;
    cin >> intCase ;
    while(intCase--){
        cin >> N >> K ;

        //debug
        //cout << N << K ;

        int intNum[N] ;

        /**< debug
        for(int i = 0 ; i < N ; i++){
            for(int j = 0 ; j < K ; j++)
                cout << intMap[i][j] << ' ' ;
            cout << '\n' ;
        }
        */

        //debug
        //print_map((int *)intMap , N , K ) ;

        for(int i = 0 ; i < N ; i++){
            for(int j = 0 ; j < K ; j++)
                intMap[i][j] = 0 ;
        }

        for(int i = 0 ; i < N ; i++)
            cin >> intNum[i] ;

        /**<//debug
        for(int i = 0 ; i < N ; i++)
            cout << intNum[i] << ' ' ;
        cout << '\n' ;
        */

        intMap[0][non_negative(intNum[0], K , 0 )] = 1 ;
        for(int i = 1 ; i < N ; i++){
            for(int j = 0 ; j < K ; j++){
                if(intMap[i-1][j]){
                    intMap[i][ non_negative(intNum[i], K , j ) ] = 1 ;
                    intMap[i][ non_negative(-intNum[i], K , j ) ] = 1 ;
                }
            }
        }

        //debug
        //print_map((int *)intMap , N , K ) ;
        //cout << intMap[N-1][0] << '\n' ;

        if(intMap[N-1][0])
            cout << "Divisible" << '\n' ;
        else
            cout << "Not divisible" << '\n' ;

    }
    return 0;
}