首页 > 代码库 > ouc 1057

ouc 1057

2024-08-02 07:27:36   217人阅读

1057: M的整数倍

时间限制: 1 Sec  内存限制: 64 MB
提交: 102  解决: 29
[提交][状态][讨论版]

题目描述

给定N个数，选出任意多的数（每个数只能选一次），使其和为M的整数倍。问最少需要选几个数。

 

输入

第一行输入一个数T代表测试用例组数（T<=10），接下来T组测试用例，每组测试用例第一行为整数M, N（1<=M, N<=1000）；接下来N行每行一个数，分别代表N个数之一。

 

输出

对于每组测试用例，输出满足条件最少需要选几个数，若没有解输出-1。每行输出一个结果。

 

样例输入

24 31112 224

样例输出

-11

提示

 

来源

第二届“朗讯杯”初级组

oooooorz 苑神#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<cmath>#include<algorithm>#include<cstdlib>#include<queue>#include<vector>#include<set>using namespace std;int t,m,n,dp[1010],a[1010],sign[1010][1010],temp;#define inf 2000000000int main(){scanf("%d",&t);while(t--){memset(dp,0,sizeof(dp));memset(a,0,sizeof(a));memset(sign,0,sizeof(sign));scanf("%d%d",&m,&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=0;i<m;i++)dp[i]=inf;for(int i=1;i<=n;i++){dp[a[i]%m]=1;sign[a[i]%m][i]=1;}for(int i=0;i<m;i++){for(int j=1;j<=n;j++){temp=(i+a[j])%m;if(sign[i][j]==0&&dp[temp]>dp[i]+1){dp[temp]=dp[i]+1;for(int k=0;k<n;k++) sign[temp][k]=sign[i][k];sign[temp][j]=1;}}}if(dp[0]==inf)printf("-1\n");elseprintf("%d\n",dp[0]);}return 0;}

　　

ouc 1057


联系
我们