lightoj 1125【背包·从n个选m个】

题意：

给你 n 个背包，然后给你两个数，D,M，问你从n个里面挑M个出来，有多少种方法能够整除D；

思路：

试想我先不挑M个出来的话，仅仅是构造一个D的倍数，其实就是构造一个数的话，

其实就是个递推，然后方案的叠加

挑M个，D的倍数。

能对M个状压；

但是对于D的倍数呢？

其实就是取膜就好了，比如5的倍数，

那么dp[个数][j]+=dp[个数-1][j-X];（个数都是状压了）

但是现在是200个里面挑10个啊。。。

不行的话就再加一维。

所以还是要从前 i 个物品推过来。。。

所以现在可以搞成dp[i][j][k]表示前i个物品选j个%D=k时的方案数；= =

每次逆推可以把第一维去掉，时间复杂度也OK；

总的来说就是：能状压么？不能解决这个事情就再开一维，一维不行上二维，二维不行三维先上了再说；（PS:n个里面选m个真是玄学。。第二遍做。。。还是碰壁GG。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

typedef pair<int,int>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<d;x++)

                        dp[j][x]+=dp[j-1][(x+d-temp)%d];

            }

            printf("%lld\n",dp[m][0]);

        }

    }

    return 0;

}

巴特西

lightoj 1125【背包·从n个选m个】

最新文章

热门文章