SS241029C. 卡路里(calorie)

题意

有 \(m\) 家奶茶店，一共有 \(n\) 种奶茶，每家店都有这 \(n\) 种奶茶。奶茶店排成一排，两两之间距离 \(d_i\)。每家奶茶店每种奶茶有一个卡路里值 \(a_{i,j}\)。选择若干家连续的奶茶店，在这些奶茶店中每种奶茶各喝一次，求最大化 \((\sum_j a_j )- (s_r-s_l)\)。其中 \(s\) 是 \(d\) 的前缀和数组。\(n\le 200,m\le 5000\)。

solution

如果你选择区间 \([l,r]\)，每种奶茶一定选择 \(\max_{i=l}^r a_{i,j}\)。

暴力 \(O(nm^2)\) 做法显然。

固定左端点 \(l\)，选择更大的右端点当且仅当多走一段距离可以得到更大的足够大 \(a\)，即使要减去距离也仍然更优。

左端点右移，选中的 \(a\) 可能会变小或者不变，你可以贪心地发现最优的右端点会单调右移。因此对于每个左端点，最优的右端点满足决策单调性。

一些并不易错点，但是记录下来：

此时我想到了二分右端点，显然错误。正确性错误。事实上只有每个左端点满足决策单调性，而二分右端点需要固定左端点时，每个右端点满足单调性。需要注意避免弄混。

此时我又想到双指针，显然错误。时间复杂度错误。同样是因为固定左端点时，右端点不满足单调性。

考虑决策单调性分治。

求出一个决策点需要遍历 \(O(m)\) 个奶茶店的。我们先求以 \(\frac{m}{2}\) 为左端点的最优决策 \(k\)。然后分治求出 \(1 \sim \frac{m}{2}-1\) 的所有决策（决策点都在 \(k\) 左边），以及 \(\frac{m}{2}+1 \sim m\) 的所有决策（决策点都在 \(k\) 右边）。每层分治求决策点一共需要遍历 \(O(m)\) 个奶茶店，一共 \(O(m\log m)\) 次遍历。遍历每个奶茶店需要 \(O(n)\) 的时间。

因此总时间复杂度是 \(O(nm\log m)\) 的。

code

注意求 \(i\) 的决策时，可选区间是 \([l,r]\)，为保证时间复杂度正确，我们只能遍历 \([l,r]\)，不能遍历完 \([i,r]\)。因此需要快速求出 \([i,l]\) 的 \(\max a_j\)。使用 st 表。注意 st 表维的顺序对程序常数时间的影响。

#include<bits/stdc++.h>
// #define LOCAL
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
#define gc getchar_unlocked
#define pc putchar_unlocked
#define isdigit(x) (x>='0'&&x<='9')
template <typename T>
void read(T &x) {
	x=0;
	T fl=1;
	char ch=gc();
	for(;!isdigit(ch);ch=gc()) if(ch=='-') fl=-1;
	for(;isdigit(ch);ch=gc()) x=(x<<3)+(x<<1)+ch-'0';
	x=x*fl;
}
template <typename T>
void write(T x,char ch) {
	static int st[20];
	int top=0;
	if(x<0) pc('-'), x=-x;
	do {
		st[top++]=x%10;
		x/=10;
	}while(x) ; 
	while(top) pc(st[--top]+'0');
	pc(ch);
}
constexpr int N=205,M=5e3+7;
int n,m;
ll d[M];
int a[M][N];
ll ans;
namespace sub3 {
	int st[15][M][N];
	void init() {
		int lg=__lg(m);
		rep(j,1,m) rep(i,1,n) st[0][j][i]=a[j][i];
		rep(k,1,lg) for(int j=1;j+(1<<k)-1<=m;j++) rep(i,1,n) st[k][j][i]=max(st[k-1][j][i],st[k-1][j+(1<<(k-1))][i]);
	}
	void findmax(int b[],int l,int r) {
		if(r<l) { return; }
		int lg=__lg(r-l+1);
		rep(i,1,n) b[i]=max(st[lg][l][i],st[lg][r-(1<<lg)+1][i]);
	}
	int b[N]; 
	int findk(int u,int l,int r) {
		l=max(l,u);
		memset(b,0,sizeof(b));
		findmax(b,u,l-1);
		ll mx=0;
		int id=0;
		rep(i,l,r) {
			rep(j,1,n) b[j]=max(b[j],a[i][j]);
			ll s=-d[i]+d[u];
			rep(j,1,n) s+=b[j];
			ans=max(ans,s);
			if(s>mx) mx=s,id=i;
		}
		return id;
	}
	void solve(int L,int R,int l,int r) {
		if(R<L) return;
		int mid=(L+R)>>1;
		int k=findk(mid,l,r);
		solve(L,mid-1,l,k), solve(mid+1,R,k,r);
	}
	void main() {
		init();
		solve(1,m,1,m);
		write(ans,'\n');
	}
}
int main() {
	#ifdef LOCAL
	freopen("my.out","w",stdout);
	#else
	freopen("calorie.in","r",stdin);
	freopen("calorie.out","w",stdout);
	#endif
	read(n),read(m);
	rep(i,2,m) read(d[i]), d[i]+=d[i-1];
	rep(i,1,m) rep(j,1,n) {
		read(a[i][j]);
	}
	sub3 :: main();
}