little shadow 2020-04-03 17:00 采纳率: 0%
浏览 211

算法 动态规划 整除运算

给出一个含有n个数字的序列,在这n个数字中间的n-1个位置任意添加加号或者减号
总共有2^(n−1) 种情况,请判断是否存在一种情况使得最后的计算结果可以整除k?

输入有多组数据
每组数据第一行有两个整数n和k(1<=n<=10000, 1<=k<=100)
第二行有n个整数表示给出的序列,每个数字的绝对值小于10000

对于每组数据输出一行
如果存在一种情况使得结果可以整除k,输出“Divisible”(不含引号)
不存在则输出“Not divisible”(不含引号)

样例输入
4 7
17 5 -21 15
4 5
17 5 -21 15

样例输出

Divisible
Not divisible

有哪位大佬能解一下吗,我写的平方阶复杂度的代码过不了

下面是我的代码

#include<iostream>
#include<vector>
#include<map>
using namespace std;
int main() {
    int n,k;
    while(cin>>n>>k) {
        map<int,int> p;//存储计算结果
        map<int,int> q;
        for(int i=-k+1;i<k;i++){
            p[i]=0;
        }
        vector<int> arr;//存储数据
        for(int i=0;i<n;i++){
            int t;
            cin>>t;
            if(t%k!=0){
                arr.push_back(t%k);
            }
        }
        if(arr.size()==0){
            cout<<"Divisible"<<endl;
            continue;
        }
        p[arr[0]]=1;
        p[-arr[0]]=1;
        for(int i=1;i<arr.size();i++){//逐步更新求得的计算结果
            for(int j=-k+1;j<k;j++){
                if(p[j]!=0){
                    q[(j+arr[i])%k]=1;
                    q[(j-arr[i])%k]=1;
                }
            }
            p.clear();
            p=q;
            q.clear();
        }
        if(p[0]==1){
            cout<<"Divisible"<<endl;
        }
        else{
            cout<<"Not divisible"<<endl;
        }
       p.clear();
       q.clear();
       arr.clear();
    }
    return 0;
}

  • 写回答

2条回答 默认 最新

  • Rotch 2020-04-03 21:52
    关注

    两个数之间必须添符号吗?还是不填符号两个数合成一个数的那种?

    评论

报告相同问题?

悬赏问题

  • ¥15 我这模型写的不对吗?为什么lingo解出来的下面影子价格这一溜少一个变量
  • ¥50 树莓派安卓APK系统签名
  • ¥15 maple软件,用solve求反函数出现rootof,怎么办?
  • ¥65 汇编语言除法溢出问题
  • ¥15 Visual Studio问题
  • ¥20 求一个html代码,有偿
  • ¥100 关于使用MATLAB中copularnd函数的问题
  • ¥20 在虚拟机的pycharm上
  • ¥15 jupyterthemes 设置完毕后没有效果
  • ¥15 matlab图像高斯低通滤波