首页 > 代码库 > DP(正解完全背包+容斥)

DP(正解完全背包+容斥)

2024-08-19 20:52:57   222人阅读

DP

Time Limit:10000MS     Memory Limit:165888KB     64bit IO Format:%lld & %llu

Submit Status

Description

　　硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买s
i的价值的东西。请问每次有多少种付款方法。

Input

　　第一行 c1,c2,c3,c4,tot 下面tot行 d1,d2,d3,d4,s,其中di,s<=100000,tot<=1000

Output

　　每次的方法数

Sample Input

1 2 5 10 23 2 3 1 101000 2 2 2 900

Sample Output

427


//背包问题，容斥原理
//不得不说这是个好题，背包问题应该都会，主要是这个容斥原理，要理解，举个例子说明下日常中经常遇到的这个定理

一次考试，某班有15人数学得满分，有12人语文得满分，并且有4人语、数都是满分，那么这个班至少有一门得满分的同学有多少人？
答案：15+12-4=23

思路是，首先不限制4种钱币的个数，看组成某个价格的方案数共有多少
然后借助容斥定理减去4种钱币超过个数限制的情况，就不多不少的求出答案

 dp[i]表示了|不限制| 硬币数目的最多付款方法，怎么转移应该都会
 那么只需将
 dp[res]
 -d1超过的限制数 - d2超过的... - d3... - d4...
 + (d1与d2) + ... + (d3与d4)
 - (d1,d2,d3)
 + (d1+d2+d3+d4)
 就行了

如果还不理解再继续看
这题的运用容斥定理，看了篇博客，例子写的很好，不然我真不太好理解，尤其是 d[i]++ 是为什么
我们来理解x=dp[s]-dp[s-(d1+1)*c1]的含义：
x 表示 c1 硬币的数量不超过 d1 个而其他三种硬币的数量不限制拼成 s 的方案数。
我们举着例子来说明，假设现在有两种硬币，面值分别为1和2，
那么我们求出 dp:dp[0]=1,dp[1]=1,dp[2]=2,dp[3]=2,dp[4]=3,dp[5]=3,dp[6]=4。
其中dp[3]的两种分别为3=1+1+1=1+2,dp[6]的四种为:6=1+1+1+1+1+1=1+1+1+1+2=1+1+2+2=2+2+2。
加入我们现在求第一种硬币最多使用两个，第二种硬币无限制的方案数，按照我们说的 x = dp[6]-dp[6--(2+1)*1]=dp[6]-dp[3]=2。
也就是6=1+1+2+2=2+2+2两种。我们发现我们删除了1+1+1+1+1+1和1+1+1+1+2两种，
为什么能够通过减去dp[3]删掉这两种？我们来看dp[3]，3=1+1+1=1+2，
我们发现6中被删掉的两种正是通过这个f[3]增加3个1得到的。

先来易懂的用for容斥的代码
技术分享
 1 #include <iostream> 2 #include <stdio.h> 3 using namespace std; 4  5 typedef long long LL; 6 #define MAX 100005 7  8 LL c[5],d[5]; 9 LL dp[MAX];10 LL ans;11 12 int main()13 {14     for (int i=1;i<=4;i++)15     scanf("%lld",&c[i]);16     int tot;17     scanf("%lld",&tot);18     dp[0]=1;19     for (int i=1;i<=4;i++)20         for (int j=c[i];j<=100000;j++)21             dp[j]+=dp[j-c[i]];22     while (tot--)23     {24         LL res;25         for (int i=1;i<=4;i++)26         {27             scanf("%lld",&d[i]);28             d[i]++;29         }30 31         scanf("%lld",&res);32         ans=dp[res];33         34         int i,j,k;35         for (i=1;i<=4;i++)36             if (res>=c[i]*d[i])37             ans-=dp[res-c[i]*d[i]];38             39         for (i=1;i<=3;i++)40             for (j=i+1;j<=4;j++)41             if (res>=c[i]*d[i]+c[j]*d[j])42             ans+=dp[res-c[i]*d[i]-c[j]*d[j]];43         for (i=1;i<=2;i++)44             for (j=i+1;j<=3;j++)45                 for (k=j+1;k<=4;k++)46                 if (res>=c[i]*d[i]+c[j]*d[j]+c[k]*d[k])47                 ans-=dp[res-c[i]*d[i]-c[j]*d[j]-c[k]*d[k]];48         if (res>=c[1]*d[1]+c[2]*d[2]+c[3]*d[3]+c[4]*d[4])49             ans+=dp[res-c[1]*d[1]-c[2]*d[2]-c[3]*d[3]-c[4]*d[4]];50 51         printf("%lld\n",ans);52 53     }54     return 0;55 }
View Code
  这个是DFS去处理容斥，简洁明了，时间是一样的
技术分享
 1 #include <iostream> 2 #include <stdio.h> 3 using namespace std; 4  5 typedef long long LL; 6 #define MAX 100005 7  8 LL c[5],d[5]; 9 LL dp[MAX];10 LL ans;11 12 void dfs(int x,int k,LL s)13 {14     if (s<0)return;15     if (x==5)16     {17         if (k%2)ans-=dp[s];18         else ans+=dp[s];19         return;20     }21     dfs(x+1,k+1,s-(d[x]+1)*c[x]);22     dfs(x+1,k,s);23 }24 int main()25 {26     for (int i=1;i<=4;i++)27     scanf("%lld",&c[i]);28     int tot;29     scanf("%lld",&tot);30     dp[0]=1;31     for (int i=1;i<=4;i++)32         for (int j=c[i];j<=100000;j++)33             dp[j]+=dp[j-c[i]];34             35     while (tot--)36     {37         LL res;38         for (int i=1;i<=4;i++)39             scanf("%lld",&d[i]);40 41         scanf("%lld",&res);42         ans= 0;43         dfs(1,0,res);44         printf("%lld\n",ans);45     }46     return 0;47 }
View Code
 
 




DP(正解完全背包+容斥)






























        

            
                
                  
                
                

                    联系

                    我们