福州网站制作建设,网页设计图片是怎么显示的,网站在线支付功能,邯郸seo优化很容易看出来是一个背包问题#xff0c;开始把每一张钞票都跑了一遍01背包#xff0c;直接TLE了。 其实就是多重背包模板题。 1 //#include bits/stdc.h2 #include iostream3 #include utility4 #include vector5 #include cstring6…很容易看出来是一个背包问题开始把每一张钞票都跑了一遍01背包直接TLE了。 其实就是多重背包模板题。 1 //#include bits/stdc.h2 #include iostream3 #include utility4 #include vector5 #include cstring6 using namespace std;7 #define fst first8 #define scd second9 #define pb(x) push_back((x))
10 #define mkp(x,y) make_pair((x),(y))
11 #define ist(x) insert((x))
12 typedef long long ll;
13 typedef pairint ,int pii;
14 typedef pairll ,ll pll;
15 typedef vector int vi;
16 ll gcd(ll a,ll b){ return b0?a:gcd(b,a%b);}
17 ll qPow(ll a,ll b,ll mod){ ll ret1ll;while(b){ if(b1) retret*a%mod;aa*a%mod;b1;} return ret; }
18
19 pii nD[13];
20 int dp[1000005];
21 int nValue;
22
23 void ZeroOnePack(int cost , int weight){
24 for(int inValue;icost;i--)
25 dp[i]max(dp[i],dp[i-cost]weight);
26 }
27
28 void CompletePack(int cost , int weight){
29 for(int icost;inValue;i)
30 dp[i]max(dp[i],dp[i-cost]weight);
31 }
32
33 void MultiplePack(int cost ,int weight,int amount){
34 if(cost*amountnValue) CompletePack(cost , weight);
35 else{
36 int k1;
37 while(kamount){
38 ZeroOnePack(k*cost,k*weight);
39 amount-k;
40 k1;
41 }
42 ZeroOnePack(amount*cost,amount*weight);
43 }
44 }
45
46 int main(){
47 int cash,N;
48 while(cincashN){
49 nValuecash;
50 memset(dp,0,sizeof(dp));
51 for(int i0;iN;i)
52 cinnD[i].firstnD[i].second;
53 for(int i0;iN;i){
54 MultiplePack(nD[i].second,nD[i].second,nD[i].first);
55 }
56 coutdp[cash]endl;
57 }
58 return 0;
59 } View Code 转载于:https://www.cnblogs.com/Kiritsugu/p/9474752.html
