首页 > 代码库 > 幸运抽奖Dp

幸运抽奖Dp

2024-07-07 04:03:24   230人阅读

题目：http://acm.hfut.edu.cn/OnlineJudge/

赛后听人说用背包搞一下，然后就搞了一下，wa到不能忍啊。注意下范围。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <string>
#include <iostream>
using namespace std;
long long  dp[60][3000];
int main()
{
    long long  n,m,k;
    while(scanf("%I64d%I64d%I64d",&n,&m,&k)!=EOF){
        for(int i=0;i<=m;i++)
            for(int j=0;j<=n*(n+1)/2;j++)
            dp[i][j]=0;
        dp[0][0]=1;
        long long  v=n*(n+1)/2;
        for(int i=1;i<=n;i++){
            for(int j=m;j>=1;j--){
                for(int t=v;t>=i;t--){
                    dp[j][t]+=dp[j-1][t-i];//取了j个物品，达到重量为t的方案数
                    dp[j][t]%=k;
                }
            }
        }
        long long  ans=0;
        for(int i=1;i<=v;i++)
            for(int j=0;j<i;j++){
                ans+=dp[m][i]*dp[m][j];
                ans%=k;//暴力枚举去 m个东西达到的重量 的种类数。
            }
        cout<<ans<<endl;
    }
    return 0;
}

　　


联系
我们