每次逆推可以把第一维去掉,时间复杂度也OK;
总的来说就是:能状压么?不能解决这个事情就再开一维,一维不行上二维,二维不行三维先上了再说;(PS:n个里面选m个真是玄学。。第二遍做。。。还是碰壁GG。
#includeusing namespace std;typedef long long LL;typedef unsigned long long ULL;typedef pair PII;const double eps=1e-5;const double pi=acos(-1.0);const int INF=0x3f3f3f3f;const int N=1e2+10;int a[N*2];LL dp[12][25];int main(){ int cas=1; int n,w,q,d,m; int t,x,sum; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&q); for(int i=1;i<=n;i++) scanf("%d",&a[i]); printf("Case %d:\n",cas++); for(int k=1;k<=q;k++) { scanf("%d%d",&d,&m); memset(dp,0,sizeof(dp)); dp[0][0]=1LL; for(int i=1;i<=n;i++) { int temp=a[i]%d; for(int j=m;j>=1;j--) for(int x=0;x