CF544C&51nod1086【限定个数的完全背包】

题意非常地晦涩难懂。

有n个程序员总共必须要码m行代码，其中每个程序员平均每行会出现的bug有x[i]个，问在总bug不超过b个的情况下有多少种方案（不是按每行是谁码的来区分，是按最终每个人码了多少行来区分）？

dp(i,j,k)：前i个程序员写了j行产生k个BUG的方案数。i省略。

#include 
#define ll long long
//#define mod 1000000007
using namespace std;
int x[505];
ll dp[505][505];
int main(){
int n,m,b,mod;
cin>>n>>m>>b>>mod;
for(int i=1;i<=n;++i)
cin>>x[i];
dp[0][0]=1;
for(int i=1;i<=n;++i){ //如果n和m的for循环位置换一换就变成是按每行是谁码的来区分
for(int j=1;j<=m;++j){
for(int k=b;k>=x[i];--k){
dp[j][k]=(dp[j][k]+dp[j-1][k-x[i]])%mod;
}
}
}
ll s=0;
for(int i=0;i<=b;++i)
s=(s+dp[m][i])%mod;
cout<return 0;
}

再看看另一道题。

有N种物品，每种物品的数量为C1，C2......Cn。从中任选若干件放在容量为W的背包里，每种物品的体积为W1，W2......Wn（Wi为整数），与之相对应的价值为P1,P2......Pn（Pi为整数）。求背包能够容纳的最大价值。

#include
#define ll long long
using namespace std;
ll w[105],p[105],c[105];
ll dp[500005];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;++i){
cin>>w[i]>>p[i]>>c[i];
}
for(int i=1;i<=n;++i){
for(int j=0;jfor(int k=m;k>=w[i];--k){
dp[k]=max(dp[k],dp[k-w[i]]+p[i]);
}
}
}
cout<return 0;
}

很可惜，这样写就要超时了。该加点什么黑科技吧。。。

解法挺奇妙的。我服。

把每种物品的个数以二进制枚举每一位选和不选，这样减少了很大的复杂度。

然而碰到一个二进制不是全1的个数怎么办？

刚才突然反应过来：假如不是全1，只要换成枚举小于等于它的全1二进制数，再单独处理零头。

#include  
#define ll long long  
using namespace std;  
ll w[105],p[105],c[105],d[105]; //c是小于等于它的全1二进制数，d是零头 
ll dp[500005];  
int main(){  
    int n,m;  
    cin>>n>>m;  
    for(int i=1;i<=n;++i){  
        cin>>w[i]>>p[i]>>c[i]; 
int u=0,s=0,p=c[i];
while(p>0){
if(p%2!=1)
u=1;
s++;
p/=2;
} 
if(u==1)
s--;
if(u==1)
d[i]=c[i]-((1<c[i]=s;
    }  
    for(int i=1;i<=n;++i){  
        for(int j=0;j            for(int k=m;k>=w[i]*(1<                dp[k]=max(dp[k],dp[k-w[i]*(1<            }  
        }  
//      for(int j=1;j<=d[i];++j){
//for(int k=m;k>=w[i];--k){
//dp[k]=max(dp[k],dp[k-w[i]]+p[i]);
//}
//}
for(int k=m;k>=w[i]*d[i];--k){ //为什么零头都算上也能对？ 
dp[k]=max(dp[k],dp[k-w[i]*d[i]]+p[i]*d[i]);
}
    }  
    cout<    return 0;  
}