题解 P1356 【数列的整数性】

· · 题解

这道题一看就是标准的DP

我们可以用背包问题的思路去做

这个程序的优点是运行速度快，内存小

为什么会快而且内存小呢

* 我们边加边模k，结果不变

* 在读入时没有将其储存，直接DP

证明思路正确如下：

设有n个数为a1，a2，a3……，an

先将其全模k得到余数

余数相加再模k

若（a1+a2-a3-a4+a5+......-an）%k==0则它们的余数（b1+b2-b3-b4+b5+......-bn）%k也为0

因为他们都是可爱的余数......

这样我们只要开101的空间就够用了（k<=100）

以下是代码（自带注释）

#include<bits/stdc++.h>//万能的头文件
using namespace std;
int n,k,e=0,nn;
int f[101],opt[101][2];
int main()
{
    scanf("%d",&nn);                                                                                                                                                                                    防抄袭
    for(int i=1;i<=nn;i++)//循环n次
    {
        memset(f,-1,sizeof(f));//数组清负1
        cin>>n>>k;//读入n和k
        f[0]=0;//f[0]可以做到
        for(int i=1;i<=n;i++)
        {
            int tmp;//读入n个数，基本不用内存
            scanf("%d",&tmp);
            tmp=(tmp%k+k)%k;//因为有负数，所以不能写tmp=tmp%k，-21%5=-1
            e=0;//第e个数
            for(int j=k-1;j>=0;j--)
            {
                if(f[j]==i-1)//因为我们要用上所有的数，所以在i-1个数都用上的时候才能进行下一次DP
                {                                                                                                                                                                                      防抄袭
                    opt[++e][0]=f[j];//精髓部分，用链表的思想储存
                    opt[e][1]=j;//同上
                    /*int tmp_fj=f[j];
                    f[(j+tmp)%k]=tmp_fj+1;
                    f[(j-tmp+k)%k]=tmp_fj+1;*/ 
                }
            }
            for(int j=e;j>=1;j--)
            {
                f[(opt[j][1]+tmp)%k]=opt[j][0]+1;//选择加这个数，边加边模k
                f[(opt[j][1]-tmp+k)%k]=opt[j][0]+1;//选择减这个数，边减边模k
            }
        }
        if(f[0]==n) puts("Divisible");//如果模0可以用n个数做到，输出Divisible
        else puts("Not divisible");//不说了
    }                                                                                           防抄袭
    return 0;
}