[Acwing] 1090. 绿色通道 单调队列优化dp+二分

前言

关于题解没有解释样例,也没解释样例看着很懵这回事 传送门 :

题意

问题转为 : 给你一个数组 a [ ] a[] a[],你可以选出任意数, 他们的和不超过 t t t

显然,你选出的数会将数组分成若干段 ,求最大的长度最小

样例解释

17    11 17\ \ 11 17  11 645   { 2 }   5   { 3 }   452   { 3 }   452   { 3 }   635 645\ \{2\}\ 5\ \{3\}\ 452\ \{3\}\ 4 52\ \{3\}\ 635 645 {2} 5 {3} 452 {3} 452 {3} 635

即得样例

思路

因为 问题字眼中存在 最大长度最小,我们考虑使用二分

首先 我们假设已经知道 最大长度 考虑 最小花费代价

显然和 1089.烽火传递,在连续长度为 m m m 至少要选一个点

因此我么们可以考虑 二分答案即 二 分 最 大 长 度 二分最大长度 二分最大长度

显然的,如果长度不满足我们需要扩大,否则缩小 ( 一眼二分性质)

因此 动态规划的状态表示没变

状态表示 f [ i ] f[i] f[i]以 i i i结尾的区间

状态计算 f [ i ] = f [ j ] m i n + w [ i ] f[i]=f[j]_{min}+w[i] f[i]=f[j]min​+w[i]

Mycode

const int N = 5e4+10;
int a[N],n,m;
int q[N];

bool check(int x){
	int dp[N] = {0};

	int hh = 0 , tt = 0 ;
	for(int i=1;i>m;
	for(int i=1;i>a[i];
	int l =0 , r= n;
	while(l>1;
		if(check(mid)) r = mid-1;
		else l = mid+1;
	}
	
	cout