HDU 2082 找单词 （多重背包）

时间：2020-12-16 04:55:27

题意:假设有x1个字母A， x2个字母B,..... x26个字母Z，同时假设字母A的价值为1，字母B的价值为2,..... 字母Z的价值为26。那么，对于给定的字母，可以找到多少价值<=50的单词呢？单词的价值就是组成一个单词的所有字母的价值之和，比如，单词ACM的价值是1+3+14=18，单词HDU的价值是8+4+21=33。(组成的单词与排列顺序无关，比如ACM与CMA认为是同一个单词）。

题解：把26个字母看做26种背包，有个数有价值，求价值不超过50的所有可能个数，就是标准的多重背包。

但是这儿我们处理时要注意：首先是枚举1到26种背包，接着要枚举价值1到50，再枚举每种背包个数

原因是：我们需要处理的是：对每种价值要用背包来求出可能个数

还有就是这儿我们求个数时，只需要把0赋值为1，其他要赋值成0

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<cmath>

#include<vector>

#include<string>

#include<cstdio>

#include<cstring>

#include<iomanip>

#include<stdlib.h>

#include<iostream>

#include<algorithm>

using namespace std;

#define eps 1E-8

/*注意可能会有输出-0.000*/

#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型

#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化

#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0

#define mul(a,b) (a<<b)

#define dir(a,b) (a>>b)

typedef long long ll;

typedef unsigned long long ull;

const int Inf=<<;

const ll INF=1ll<<;

const double Pi=acos(-1.0);

const int Mod=1e9+;

const int Max=;

ll dp[Max],val[Max];

ll Pack(int n)

{

    for(int i=; i<; ++i)

        dp[i]=0ll;

    dp[]=1ll;

    for(int i=; i<=n; ++i)

    {

        for(int j=; j>; --j)

        {

            for(int k=; k<=val[i]; ++k)

            {

                if(j-k*i>=)

                    dp[j]+=dp[j-k*i];

            }

        }

    }

    ll sum=0ll;

    for(int i=; i<; ++i)

        sum+=max(dp[i],0ll);

    return sum;

}

int main()

{

    std::ios::sync_with_stdio(false);

    int t;

    cin >> t;

    while(t--)

    {

        for(int i=; i<=; ++i)

            cin >> val[i];

        cout << Pack() << endl;

    }

    return ;

}

相关文章