2023.3.14 状压 dp 模拟赛题解

好强啊。不说是谁了，都好强啊呜呜呜。

 首先 T1 的一个优化 luogu P1842 奶牛玩杂技，需要一个贪心排序来优化序列顺序。关于贪心排序：像这样有两种及以上性质的序列，注意以哪个为关键字排列。两道题的顺序都是：x.s + x.w > y.s + y.w。一定会优先选又重又强壮的奶牛垫在下面。

两种做法：1.dfs。爆搜加上各种优化剪枝就会把时间复杂度降到很小。代码是找同学要的，太强了我今天才刚会写 dfs，这种剪枝第一次见真就叹为观止！

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int N = 22;
 5 int n, flag = 0;
 6 ll h, ans = 0;
 7 int sumh[N], sumw[N];
 8 struct Cow {ll h, w, s;} a[N];
 9 
10 bool cmp(Cow x, Cow y){return x.s + x.w > y.s + y.w;}
11 
12 void dfs(int i, ll high, ll tot)
13 {
14     if(high >= h)
15     {
16         flag = 1;
17         ans = max(ans, tot);
18         return ;
19     }
20     if(i > n) return ;
21     if(ans >= tot) return ;
22     if(high + sumh[n] - sumh[i - 1] < h) return ;
23     if(a[i].w <= tot) dfs(i + 1, high + a[i].h, min(a[i].s, tot - a[i].w));
24     if(tot) dfs(i + 1, high, tot);
25 }
26 
27 int main()
28 {
29     scanf("%d%lld", &n, &h);
30     for(int i = 1; i <= n; i ++ ) scanf("%lld%lld%lld", &a[i].h, &a[i].w, &a[i].s);
31     sort(a + 1, a + n + 1, cmp);
32     for(int i = 1; i <= n; i ++ )
33     {
34         sumh[i] = sumh[i - 1] + a[i].h;
35         sumw[i] = sumw[i - 1] + a[i].w;
36     }
37     dfs(1, 0, 0x3f3f3f3f);
38     if(flag) printf("%lld", ans);
39     else printf("Impossible");
40     return 0;
41 }

 2.状态压缩 dp

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int N=21;
 5 const int inf=0x3f3f3f3f;
 6 int n;
 7 ll m, tot, maxn = -1;
 8 int r[N];
 9 struct node {ll h,w,s;} a[N];
10 bool cmp(node a,node b) {return a.s + a.w > b.s + b.w;}
11 ll check()
12 {
13     ll sum = 0, high = 0, ans = inf;
14     for(int i = 1; i <= tot; i ++ )
15     {
16         sum = 0;
17         for(int j = i + 1; j <= tot; j ++ ) sum += a[r[j]].w;
18         if(sum > a[r[i]].s) return -1;
19         high += a[r[i]].h;
20         ans = min(ans, a[r[i]].s - sum);
21     }
22     if(high < m) return -1;
23     return ans;
24 }
25 int main()
26 {
27     scanf("%d%lld",&n,&m);
28     for(int i = 0; i < n; i ++ ) scanf("%lld%lld%lld", &a[i].h, &a[i].w, &a[i].s);
29     sort(a, a + n, cmp);
30     for(int s = 1; s < 1 << n; s ++ )
31     {
32         tot = 0;
33         for(int i = 0; i < n; i ++ ) if(s & 1 << i) r[ ++ tot] = i;
34         maxn = max(maxn, check());
35     }
36     if(!maxn) printf("Impossible\n");
37     else printf("%lld", maxn);
38     return 0;
39 }