关于单调队列优化dp
  • 板块学术版
  • 楼主sinsop90
  • 当前回复4
  • 已保存回复4
  • 发布时间2021/11/15 19:15
  • 上次更新2023/11/4 00:28:37
查看原帖
关于单调队列优化dp
141599
sinsop90楼主2021/11/15 19:15

为什么要取队列头减一啊?

例:P5665划分

for(int i = 1;i <= n;i++) {
		while(l <= r && pre[i] - pre[q[l]] >= g[q[l]]) l ++;
		f[i] = f[q[l - 1]] + (pre[i] - pre[q[l - 1]]) * (pre[i] - pre[q[l - 1]]);//取的是队列头减一
		g[i] = pre[i] - pre[q[l - 1]];
		while(l <= r && g[q[r]] + pre[q[r]] > g[i] + pre[i]) r --;
		q[++r] = i;
	}

为啥捏, 可能我脑子出了点问题, 有人嫩解释一下嘛

2021/11/15 19:15
加载中...