Atcoder abc310

發表於 更新於 分類於 ， Disqus： 文章字數： 1k 所需閱讀時間 ≈ 3 分鐘
Ex(抽屉原理)

https://atcoder.jp/contests/abc310/tasks

Ex - Negative Cost

$h \in [1,10^{18}]$

p = 0

n个($[1,300]$) $c_i [-300,300]$,$d_i [1,10^9]$

每次可以 任选一个p(可重复选), 满足$p \ge c_i$, 然后 $p -= c_i$, $h -= d_i$

问最少多少次 让 $h \le 0$

3s

1024mb

我的思路

先预处理数据

sort pair{ci,di}

对于 $c_i \le c_j, d_i \ge d_j$, 舍去 {cj,dj}

因为首先单次ci代价越小,di越多越好

dp[i][t][p] = 前i个 操作t次, p的结束值 能消耗最大的h

dp[i][t+k][p-k*ci] = max dp[i-1][t][p]

显然空间都存不下

考虑预处理后的数据

排序后前部分的 -k*ci > 0

题解

$L=300$,是 |c|的上界

也是 简化一下题意,就是选择的前缀 -C的和 $\ge 0$

令 所有前缀和 $\le 2L$,的方案为 basic方案

性质1, 任何合法方案 可以转换称对应的basic方案

c: [...](>=L) >0, <0, 则交换后两个,这样保证了 前缀和合法的情况下,拆成[.......<0]一段basic和很多 >=0的单个basic

性质2: basic方案 可以拆分成 多个 长度不大于2L的

因为前缀和 <= 2L, 所以容斥原理存在两个前缀相同

[....][...=0][...], 把中间这段拆出来sort一下再拆分,两端直接拼接,可以无限递归下降直到长度<=2L

综上, 变成了任何方案 一定可以拆分成 多个 长度<=2L, 且 前缀和保持 [0,2L]的段的拼接

满足上述情况下

dp[i][j] = 长度i,和为j的最大 D的消耗

2L 2L个状态,转移代价n倍

处理后 问题变为 2L个东西,第i个东西代价i,消耗Di,要让 代价和 尽量小,消耗和 >= h

令z={代价,消耗}是上面2L东西中di/i最大的,用它来拼h,可以完成,但不一定最优

而在最优的方案中,如果存在2L个不是z的

那么这2L的组合的 代价和 取mod z.代价.再次抽屉原理 至少有两个前缀是mod z.代价相同的,那它们之间的差是z.代价的倍数, 替换成z不会更差

所以 最优方案中, 最多有<2L个不使用z

所以现在 如果不一定用z的消耗和为$h_0$,那么剩余用z,就是$\lceil \frac{h-h_0}{h}\cdot z_{代价}\rceil$的代价

dp2[i][j], 用前i个东西,代价和为j的最大消耗,注意到j的范围在 $(2L)^2$, O(1)转移代价

代码

https://atcoder.jp/contests/abc310/submissions/48959505

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
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f'3f3f3f3f;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
ll read(){ll r;scanf("%lld",&r);return r;}
const int C = 300;
int main(){
  int n=read(); // 300
  ll h=read(); // 1e18
  vector<array<ll,2> > cd(n); // -300~300, 1e9
  rep(i,0,n) {
    cd[i][0]=read();
    cd[i][1]=read();
  }
  auto setMax=[](auto&a,auto b){ a=max(a,b); };
  // dp[个数][c的和]=最大伤害,最优方案总能切割长个数<=2C,前缀保持<=2C的多个段
  vector dp(2*C+1,vector<ll>(2*C+1,-INF));
  dp[0][0] = 0;
  vector<ll> D(2*C+1,-INF); // D[个数] = 最大伤害, 2*300*1e9
  rep(j,0,2*C) for(auto [c,d]:cd) rep(s,0,2*C+1) if(dp[j][s] != -INF) // 先for个数
      if(s - c >= 0 and s - c <= 2*C) setMax(dp[j+1][s-c], dp[j][s]+d);
  rep(j,0,2*C+1) rep(s,0,2*C+1) if(dp[j][s] != -INF) setMax(D[j], dp[j][s]);
  int besti = 1;
  rep(i,2,2*C+1) if(D[i]*besti > D[besti]*i) besti = i; // D[i]/i > D[besti]/besti, 600^2*1e9
  const int mxS = (2*C*2*C);
  vector dp2(mxS+1,-INF); // dp2[代价和j <= 2C*2C] = 最大伤害
  dp2[0] = 0;
  ll ans = INF;
  rep(i,1,2*C+1) rep(j,0,mxS) if(dp2[j] != -INF) if(j + i <= mxS) setMax(dp2[j+i],min(dp2[j]+D[i],INF));
  auto ceildiv=[](ll a,ll b){return a/b+!!(a%b);};
  rep(j,1,mxS+1) if(dp2[j] != -INF) {
    if(dp2[j] >= h) ans = min(ans,j);
    else            ans = min(ans,j+ceildiv(h-dp2[j],D[besti])*besti);
  }

  printf("%lld\n",ans);
  return 0;
}

总结

Ex

这两个性质推断的方向,看得我一愣一愣的

后面两次的抽屉原理得到性质,也自己没有想到

参考

官方题解