ACM UVA 10036 (Problem C: Divisibility)

题目：

思路：

整除+DP

将输入存放在数组input[10000]中。
remains[100]用来保存当前的状态(计算到input[i]时，当前所有可能的余数)。利用remains计算出 加或者减input[i+1]后，所有的余数。并将这些余数再次存放在remains中。到计算完input[N-1]后，如果remains保存的余数中存在0，那么就能整除。

代码：

#include <iostream>
#include <cstring>

using namespace std;

inline int ABS(int v)
{
    if (v < 0) {
        v = 0 - v;
    }
    return v;
}

int main()
{
    int caseCount = 0;
    int remains[100];
    int remainsTmp[100];
    int input[10000];

    cin >> caseCount;
    for (; caseCount != 0; caseCount--) {
        int N, K;
        cin >> N >> K;
        for (int i = 0; i < N; i ++) {
            cin >> input[i];
        }

        memset(remains, 0, 100*sizeof(int));
        int x = input[0] % K;
        if (x < 0) {
            x = K + x;
        }
        remains[x] = 1;
        
        for (int i = 1; i < N; i++) {
            memset(remainsTmp, 0, sizeof(int)*100);
            for (int j = 0; j < 100; j++) {
                if (remains[j] == 1) {
                    int m1 = (j+input[i]) % K;
                    if (m1 < 0) {
                        m1 = K + m1;
                    }
                    int m2 = (j-input[i]) %K;
                    if (m2 < 0) {
                        m2 = K + m2;
                    }
                    //cout << m1 << " " << m2 << endl;
                    remainsTmp[m1] = 1;
                    remainsTmp[m2] = 1;
                }
            }
            //cout << endl;
            memcpy(remains, remainsTmp, sizeof(int)*100);
        }

        if (remains[0] == 1) {
            cout << "Divisible";
        } else {
            cout << "Not divisible";
        }
        if (caseCount != 0) {
            cout << endl;
        }
    }
}