OI题解 - Yakiniku Restaurants (Atcoder)

这段时间复习DP优化~
还是比较顺手(除了那万恶的没有单调性的斜率优化……)


# 题意

在一条街(近似地看作坐标轴)上有 n 家烧烤店,每家店都有 m 种烧烤套餐。
你现在有 m 张卷,使用第 i 张卷可以在任意店品尝一次第 i 种套餐(你也可以在一家店吃多种套餐,但是每种卷只能用一次)。

第 i 家店在位置 $x_i$,它提供的第 j 种套餐的美味值是 $w_{i,j}$。

你想品尝尽可能美味的烧烤,但是又不希望走太远的路,因此你希望知道:“品尝的所有套餐的美味值之和-行走的总距离”最大是多少。注意,你可以从任意一家店出发


# 解析

很容易想到贪心——因为走过的店一定是连续的一个区间,所以你吃的第 j 种套餐一定是这个区间的所有饭店提供的第 j 种套餐中最美味的。而且需要走过的路程就是这个区间的长度(从左到右走一遍就可以了)。

所以可以得到,如果走过的店的区间为 $[l,r]$,则答案为:

那么对于每个 $r$,我们希望迅速地找到一个使 $f(l,r)$ 最大的 $l$。如果你试过打表,那么你会发现 $r$ 增大时,对应的使 $f(l,r)$ 最大的 $l$ 也会增大(严谨地说是“不会减小”)。但是为什么?

# 证明

不失一般性地假设 $m=1$。
设 $r_1$ 对应的左端点为 $l_1$,$r_2$ 对应 $l_2$,且 $r_1<r_2$。则需证明 $l_1\le l_2$。
记 $A=\max_{i=l_1}^{l_2-1}w_{i,1}$,$B=\max_{i=l_2}^{r_1}w_{i,1}$,$C=\max_{i=r_1+1}^{l_2}w_{i,1}$。也就是这样:

jpg1

看起来很像四边形不等式?Right~

首先排除掉 $A<B$ 的情况,这种情况 $r_2$ 对应 $l_1$ 会更优(懒得证明了……)也就是说 $B<A$(等号能不能不管嘛……讨论起来麻烦)

于是分类讨论:

  1. $C<B<A$:

    可得 $f(l_1,r_1)+f(l_2,r_2)=A+B-r_1-r_2+l_1+l_2=f(l_1,r_2)+f(l_2,r_1)$。

  2. $B<C<A$:

    $f(l_1,r_1)+f(l_2,r_2)=A+C-r_1-r_2+l_1+l_2$;

    $f(l_1,r_2)+f(l_2,r_1)=A+B-r_1-r_2+l_1+l_2$;

    所以 $f(l_1,r_1)+f(l_2,r_2)>f(l_1,r_2)+f(l_2,r_1)$

  3. $B<A<C$:

    $f(l_1,r_1)+f(l_2,r_2)=A+C-r_1-r_2+l_1+l_2$;

    $f(l_1,r_2)+f(l_2,r_1)=B+C-r_1-r_2+l_1+l_2$;

    所以 $f(l_1,r_1)+f(l_2,r_2)>f(l_1,r_2)+f(l_2,r_1)$;

综上,四边形不等式成立,具有单调性。

所以~ 决策单调性分治优化(你也可以写二分栈,但是这道题既然可以分治……那还是简单一点好 awa)


# 源代码

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/*Lucky_Glass*/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=5000,M=200;

int n,m;
int rB[N+3][M+3][14],Log2[N+3];
long long rA[N+3];

inline int QRead(){
register int resu=0;register char ch=getchar();
while(ch<'0' || '9'<ch) ch=getchar();
while('0'<=ch && ch<='9')
resu=(resu<<1)+(resu<<3)+ch-'0',
ch=getchar();
return resu;
}
long long Calc(int l,int r){
long long resu=0;
int len=(int)Log2[r-l+1];
for(int j=1;j<=m;j++){
resu+=max(rB[l][j][len],rB[r-(1<<len)+1][j][len]);
}
return resu;
}
long long Solve(int il,int ir,int kl,int kr){
if(il>ir) return -1;
int i=(il+ir)>>1,tra=0;
long long resu=0;
for(int k=kl;k<=kr && k<=i;k++){
long long now=Calc(k,i)-(rA[i-1]-rA[k-1]);
if(now>resu){
resu=now;
tra=k;
}
}
return max(resu,max(Solve(il,i-1,kl,tra),Solve(i+1,ir,tra,kr)));
}
int main(){
n=QRead();m=QRead();
for(int i=1;i<n;i++) rA[i]=QRead()+rA[i-1];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
rB[i][j][0]=QRead();
Log2[1]=0;
for(int i=2;i<=n;i++)
Log2[i]=Log2[i>>1]+1;
for(int k=1;k<14;k++){
for(int j=1;j<=m;j++)
for(int i=1;i<=n;i++){
if(i+(1<<k-1)<=n)
rB[i][j][k]=max(rB[i][j][k-1],rB[i+(1<<k-1)][j][k-1]);
else
rB[i][j][k]=rB[i][j][k-1];
}
}
printf("%lld\n",Solve(1,n,1,n));
return 0;
}

The End

Thanks for reading!

CSP结束回到边训练边补文化课的状态……感觉还是没有完全适应呢?

0%