【AtCoder】[Regular Contest 067 F] Yakiniku Restaurants

Qizy 动态规划, 杂项, 解题报告

相关链接

题目传送门：http://arc067.contest.atcoder.jp/
官方题解：https://arc067.contest.atcoder.jp/editorial

解题报告

因为区间的选择会同时影响所有颜色
所以肯定不可能按颜色来分开计算

考虑枚举右端点，左端点从左向右扫
每一种餐票的最终贡献一定是单调不增的
于是使用单调队列维护这个东西
在转折点的地方打个差分
因为差分的值不受颜色类型的影响，所以不分颜色
于是直接暴力扫左端点就可以了
时间复杂度：$ O({n^2})$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 5000+9;
const int M = 200+9;

int n,m,que[M][N],cnt[M],mat[M][N],bst[M];
LL delta[N],x[N],vout,cur,dis,len;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int main() {
	n = read(); m = read();
	for (int i=1;i<n;i++) 
		x[i] = read();
	for (int j=1;j<=n;j++) {
		for (int i=1;i<=m;i++) {
			mat[i][j] = read();
		}
	}
	for (int r=1;r<=n;r++) {
		cur = 0; len = (dis += x[r-1]);
		for (int i=1;i<=m;i++) {
			while (cnt[i] && mat[i][que[i][cnt[i]]] <= mat[i][r]) {
				if (cnt[i] > 1) 
					delta[que[i][cnt[i]-1]] += mat[i][que[i][cnt[i]-1]] - mat[i][que[i][cnt[i]]];
				cnt[i]--;
			}
			que[i][++cnt[i]] = r;
			if (cnt[i] > 1) delta[que[i][cnt[i]-1]] += mat[i][r] - mat[i][que[i][cnt[i]-1]];
			bst[i] = max(bst[i], mat[i][r]);
			cur += bst[i];
		}
		for (int l=1;l<=r;l++) {
			vout = max(vout, cur - len);
			cur += delta[l];
			len -= x[l];
		}
	}
	printf("%lld\n",vout);
	return 0;
}

13 thoughts to “【AtCoder】[Regular Contest 067 F] Yakiniku Restaurants”

  3. 641022 582057Not long noticed concerning your web website and are nonetheless already reading along. I assumed ill leave my initial comment. i do not verify what saying except that Ive enjoyed reading. Nice blog. ill be bookmarking maintain visiting this web website actually typically. 428854

    Reply

  7. 806727 825484Hello. I wanted to ask one thingis this a wordpress web site as we are preparing to be shifting more than to WP. Furthermore did you make this template yourself? Thanks. 963866

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *