百度之星2022 初赛

發表於 更新於 分類於 Disqus： 文章字數： 473 所需閱讀時間 ≈ 2 分鐘
积木BD202205(LCM)

积木 BD202205

似乎测试数据太弱了

题意 给定a[1..10] <= 1e11, h <= 1e12

对于任意b, 求min(max(sum b[i] * i), h), b[i] \in [0,a[i]] b[i]是整数

2s

512mb

我的思路

似乎没官方题解

我最开始想的用bitmask, 去做 dp, 按照不同顺序，有贪心最多

但是实际上 h=10, a[2] = 3, a[3] = 3时

选2个2和2个3刚好拼成10, 而贪心 会是 3 * 2 + 1 * 3 或者 0 * 2 + 3 * 3 都无法达到最大

然后测试数据弱就过了，根据讨论区 说，只要所有加起来都能过测试，这是什么坑爹的出题人和数据，

新的思路

lcm 下的表示

如果暴力 dp就是dp[前i个][和为j] = 能否达到

LCM = lcm(1..10)

而注意到 如果

  • dp[i][j] 可以从 dp[i-1][j0],达到
  • dp[i-1][j0+LCM] 是可达的
  • j >= j0+LCM

这三个条件同时满足， 则dp[i][j] 可以从 dp[i-1][j0+LCM]达到!

因此 变成 dp[前i个用完][val%LCM = j]= 最大可达的val (且<=h)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
ll read(){ll r;scanf("%lld",&r);return r;}
const ll INF = 0x3f3f3f3f'3f3f3f3f;
const int bound = 2520; // lcm(1..10);
ll cnt[20];
int main(){
  ll h = read();
  rep(i,1,10+1) cnt[i] =read();
  auto maxt = [&](ll v,ll i){ return min(cnt[i], (h-v)/i); };
  auto setmax = [](ll &a,ll b){a=max(a,b);};
  vector<ll> mx(bound, -INF); // mx[i] 表示  <= h 范围内, 满足val mod bound == i 的最大可达val
  mx[0] = 0;
  rep(i,1,10+1) {
    vector<ll> newmx(bound, -INF);
    rep(modv,0,bound) if(mx[modv] != -INF){
      // v + i * k <= h
      // 0 <= k <= cnt[2]
      ll v = mx[modv];
      ll maxk = maxt(v,i);
      rep(k,max((ll)0,maxk+1-bound), maxk+1){
        ll newv = v + i * k;
        setmax(newmx[newv%bound],newv);
      }
    }
    mx=newmx;
  }
  ll ans = 0;
  rep(modv,0,bound) if(mx[modv] != -INF) ans = max(ans,mx[modv]);
  printf("%lld\n",ans);
  return 0;
}

感觉 似乎还是没有完全的证明到