目录

1. P2050
2. P1169

正文

P2050 [NOI2012] 美食节 | 费用流

首先可以发现第 \(i\) 个厨师做他的第 \(j\) 个菜，时间可以表示为 \(j\times t\)。于是可以把厨师分成 \(mp\) 个点 \((i=1\dots m,j=1\dots p)\)。当 \((i,j)\) 被增广的时候，才加点 \((i,j+1)\)，减少边数。用最大流控制所有菜都被做，然后用最小费用求出最小时间和。

P1169 [ZJOI2007]棋盘制作 | 动态规划、单调栈

第一问略。

对于第二问，先预处理出每个点向上、向左、向右最远能合法到达的长度，记作 \(uv_{i,j},lv_{i,j},rv_{i,j}\)。可以发现最终答案的竖向长度一定在 \(uv\) 中。于是枚举行 \(i\) 列 \(j\)，用单调栈求出每个 \(uv_{i,j}\) 向左最远到 \(k\) 才会满足 \(uv_{i,j}>uv_{i,k}\)，向右亦然。然后就可以通过 \(lv_{i,j}\) 和 \(k\) 求出向左的最大矩形了。

For(i,1,n){
	stk.top=0;
	For(j,1,m){
		while(stk.top&&uv[i][stk.s[stk.top]]>=uv[i][j]) --stk.top;
		chkmax(ans2,min((j-stk.s[stk.top]),lv[i][j])*uv[i][j]);
		stk.s[++stk.top]=j;
	}
	stk.top=0;
	Dec(j,m,1){
		while(stk.top&&uv[i][stk.s[stk.top]]>=uv[i][j]) --stk.top;
		chkmax(ans2,min((stk.top?stk.s[stk.top]:m+1)-j,rv[i][j])*uv[i][j]);
		stk.s[++stk.top]=j;
	}
}