POJ 1745 Divisibility 很好的DP题 yongmou

题意：n个整数中间填上+或者-，运算结果能否被k整除。1<=n<=10000, 2<=k<=100

思路：虽然不是最优化问题，但确实是DP，刚开始我也没想起了怎么DP。可以把结果mod k看作状态，这样虽然n个数有2^n-1种运算方式，但结果只有k种，所以只需枚举这k个数即可。

f(i, j) 表示 前i个数运算结果mod k是否存在余数j，转移方程就简单了：如果f( i-1, j)为true，那么把f(i, (j+a[i])mod k)和f(i, (j-a[i])mod k)置真。

代码：

#include<cstdio>
using namespace std;

int n, k;
bool dp[10000][100];

int mod(int m, int k){
    if(m>=0)
        return m % k;
    return ((-m/k + 1)*k + m) % k;
}

void process(){
    int i, j;
    for(i=0; i<n; ++i)
        for(j=0; j<k; ++j)
            dp[i][j] = 0;
    int a;
    scanf("%d", &a);
    dp[0][mod(a, k)] = true;
    for(i=1; i<n; ++i){
        scanf("%d", &a);
        for(j = 0; j<k; j++){
            if(dp[i-1][j]){//在之前的的运算中得到了
                int tmp;
                tmp = mod(j+a, k);
                dp[i][tmp] = true;
                tmp = mod(j-a, k);
                dp[i][tmp] = true;
            }
        }
    }
}

int main(){
//    freopen("in", "r", stdin);

    int case_num;
    scanf("%d", &case_num);
    while(case_num--){
        scanf("%d %d", &n, &k);

        process();

        if(dp[n-1][0])
            printf("Divisible\n");
        else
            printf("Not divisible\n");
    }
}