DP-UVA 10036-Divisibility

桃扇骨 2022-05-14 22:22 129阅读 0赞

*  # DP-UVA 10036-Divisibility #

--------------------

*  ## 题目链接： ##

### [10036 - Divisibility][] ###

*  ## 思路： ##

给N个数，在数与数之间，可以是 +号 或 -号，对各种可能的加减号分布情况 的运算式进行计算，如果其中有结果被K整除，输出 Divisible ，否则输出Not divisible

刚开始想暴力递归出全部结果，后来TLE。。。

正确做法是递归，对一个数运算，除了开头，要么是加要么是减，对每次运算都标记所得余数，如果运算完最后一个数时余数为0，为 Divisible

有一个数学上的问题，就，整体取模和部分取模最后结果是一样是，模运算也特别好用，比如这道题，对每一步运算都取模，可以把宽度压缩到K，只要判断终点 DP\[N-1\]\[0\] ，如果终点（余数为0）标记true，说明结果能被K整除

而且，负数转正后取模也是不影响结果

**状态转移方程： DP\[i\]\[abs(j+Num\[i\])%K\]=true; （j是上一轮计算所得余数）  
DP\[i\]\[abs(j-Num\[i\])%K\]=true;**

*  ## 代码： ##

#include<iostream>
    #include<cmath>
    #include<memory.h>
    using namespace std;
    #define MAX_SIZE 10005
    bool DP[MAX_SIZE][105];
    int Num[MAX_SIZE];
    
    int main()
    {
        int N,K;
        int T;
        cin>>T;
        while(T--)
        {
            memset(DP,false,sizeof(DP));
            cin>>N>>K;
            for(int i=0;i<N;i++)
            {
                cin>>Num[i];
                Num[i]=abs(Num[i])%K;
            }
            DP[0][Num[0]]=true;
            for(int i=1;i<N;i++)
            {
                for(int j=0;j<K;j++)
                {
                    if(DP[i-1][j])
                    {
                        DP[i][abs(j+Num[i])%K]=true;
                        DP[i][abs(j-Num[i])%K]=true;
                    }
                }
            }
            if(DP[N-1][0])
                cout<<"Divisible"<<endl;
            else
                cout<<"Not divisible"<<endl;
        }
        return 0;
    }

[10036 - Divisibility]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=977