BAPC2018 KALLAX Construction

Sample Input2

371
3
2 40 65
2 100 150
2 300 320

Sample Output2

impossible

Sample Input3

90
2
2 20 35
2 88 200

Sample Output3

88

Sample Input4

91
2
2 20 35
2 88 200

Sample Output4

200

背包问题。

  1 #include<iostream>
  2 #include<sstream>
  3 #include<fstream>
  4 #include<algorithm>
  5 #include<cstring>
  6 #include<iomanip>
  7 #include<cstdlib>
  8 #include<cctype>
  9 #include<vector>
 10 #include<string>
 11 #include<cmath>
 12 #include<ctime>
 13 #include<stack>
 14 #include<queue>
 15 #include<map>
 16 #include<set>
 17 #define mem(a,b) memset(a,b,sizeof(a))
 18 #define random(a,b) (rand()%(b-a+1)+a)
 19 #define ll long long
 20 #define ull unsigned long long
 21 #define e 2.71828182
 22 #define Pi acos(-1.0)
 23 #define ls(rt) (rt<<1)
 24 #define rs(rt) (rt<<1|1)
 25 #define lowbit(x) (x&(-x))
 26 using namespace std;
 27 const int MAXN=2e3+5;
 28 ll dp[MAXN];
 29 ll a[MAXN],b[MAXN],c[MAXN];
 30 ll B,k,l;
 31 ll read()
 32 {
 33     ll s=1,x=0;
 34     char ch=getchar();
 35     while(!isdigit(ch)) {if(ch=='-') s=-1;ch=getchar();}
 36     while(isdigit(ch)) {x=10*x+ch-'0';ch=getchar();}
 37     return x*s;
 38 }
 39 void fun(int n)
 40 {    
 41     mem(dp,-1ll);
 42     dp[0]=0;
 43     
 44     for(int i=1;i<=n;++i)
 45     {
 46         for(int j=0;j<=MAXN-a[i];++j)
 47         {
 48             if(dp[j]<0) continue;
 49             int real=dp[j]+b[i];
 50             if(dp[j+a[i]]<0 || dp[j+a[i]]>real)
 51             dp[j+a[i]]=real;
 52         }
 53     }
 54 } 
 55 int main()
 56 {
 57     B=read(),k=read();
 58     bool flag=false;
 59     ll ans=1ll<<60;
 60     int lastnum;
 61     mem(dp,-1ll);
 62     dp[0]=0;
 63     for(int p=1;p<=k;p++)
 64     {
 65         l=read();
 66         if(p>1) for(int i=1;i<=lastnum;++i) a[i]=c[i];//false
 67         for(int i=1;i<=l;++i) c[i]=read();
 68         if(p==1) 
 69         {
 70             for(int i=1;i<=l;++i) 
 71             {
 72                 b[i]=c[i];//true
 73             }
 74         }
 75         else
 76         {
 77             fun(lastnum);
 78             
 79             for(int i=1;i<=l;++i)
 80             {
 81                 for(int j=c[i];j<MAXN;++j)
 82                 if(dp[j]>=0) 
 83                 {
 84                     b[i]=dp[j];
 85                     break;
 86                 }
 87             }
 88         }
 89         for(int i=1;i<=l;++i)
 90         {
 91             if(b[i]>=B)
 92             {
 93                 ans=min(ans,c[i]);
 94                 flag=true;
 95             }
 96         }
 97         lastnum=l;
 98     }
 99     
100     if(flag) cout<<ans<<endl;
101     else cout<<"impossible
";
102 }

View Code

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 using ll = long long;
 5 using ii = pair<long, long>;
 6 using vi = vector<ll>;
 7 using vvi = vector<vi>;
 8 using vii = vector<ii>;
 9 using vvii = vector<vii>;
10 
11 constexpr int BMAX = 2001;
12 
13 int main() {
14     ios::sync_with_stdio(false);
15     cin.tie(nullptr);
16 
17     ll B;
18     int K;
19     cin >> B >> K;
20 
21     vvii prices(K);
22     
23     for (int i = 0; i < K; ++i) {
24         vi dp(BMAX+1, -1LL);
25         dp[0] = 0LL;
26 
27         if (i > 0) {
28             for (ii price : prices[i-1]) {
29                 ll sticker, real;
30                 tie(sticker, real) = price;
31                 for (int j = 0; j <= BMAX - sticker; ++j) {
32                     if (dp[j] >= 0LL) {
33                         ll new_real = dp[j] + real;
34                         if (dp[j+sticker] > new_real || dp[j+sticker] < 0)
35                             dp[j+sticker] = new_real;
36                     }
37                 }
38             }
39         }
40         int L, N;
41         cin >> L;
42         while (L--) {
43             cin >> N;
44             if (i == 0)
45                 prices[i].push_back({N, N});
46             else {
47                 for (int j = N; j <= BMAX; ++j)
48                     if (dp[j] >= 0LL) {
49                         prices[i].push_back({N, dp[j]});
50                         break;
51                     }
52             }
53         }
54         
55         
56     }
57     
58     ll ans = -1LL;
59     for (int i = 0; i < K; ++i)
60         for (ii price : prices[i])
61             if (price.second >= B)
62                 ans = (ans < 0LL || ans > price.first ? price.first : ans);
63     if (ans == -1LL) cout << "impossible" << endl;
64     else cout << ans << endl;
65 }

View Code