UVA1619 感觉不错 Feel Good（良好的感觉）题解

0.题面：

给出正整数n和一个(1 <= n <= 100 000)长度的数列，要求找出一个子区间，使这个子区间的数字和乘上子区间中的最小值最大。输出这个最大值与区间的两个端点。

1.思路

一开始试图使用单调栈，然而在调试一上午无果后愤然打了个分治，然后就过了233

根据分治三步法，算法流程分为：

1.分解：定义 \(dfs(l,r)\) 为区间 \([l,r]\) 的最优解，\(mid = (l+r)/2\) ，可以把问题分为 \(dfs(l,mid)\) 和 \(dfs(mid+1,r)\) 两部分，分别对应最优解完全位于左子区间和右子区间的情况。

2.边界：当 \(l=r\) 时，\(dfs(l,r)={a_l}^2\)。（数列为\(a\)）

3.合并：在第一步处理了最优解完全位于左子区间和右子区间的情况，还有最优解跨越 \(mid\) 的情况没处理。注意到当最小值一定时，区间越大越好，所以可以从大到小地选择最大值，再从中点开始往左右两端“放宽”当前区间。

2.Code

#include <bits/stdc++.h>

using namespace std;

#define MAXN 1000000

typedef long long ll;

int n;

ll a[MAXN+5],sum[MAXN+5],ans;

struct answ{

	int l,r;ll v;

	answ(){

		l=r=v=0;

	}

	answ(int L,int R,ll V){

		l=L;r=R;v=V;

	}

};

bool operator < (answ l,answ r){

	return l.v<r.v;

}

struct ST{

	ll st[MAXN+1][31];

	int query(int l,int r){

        int k=log2(r-l+1);

        return min(st[l][k],st[r-(1<<k)+1][k]);

    }

    void build(){

    	for(int i=1;i<=n;i++){

    		st[i][0]=a[i];

		}

    	for(int j=1;j<=30;j++){

            for(int i=1;i+(1<<j)-1<=n;i++){

                st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);

            }

        }

	}

}qwq;

ll query(int l,int r){

	return qwq.query(l,r)*(sum[r]-sum[l-1]);

}//求一个区间的“数字和乘上子区间中的最小值”

answ dfs(int l,int r){//分治主体

	int mid=(l+r)/2;

	if(l==r){//边界

		return answ(l,r,query(l,r));

	}

	answ ans=max(dfs(l,mid),dfs(mid+1,r));

	vector<int> tmp;

	for(int i=l;i<=r;i++){

		tmp.push_back(a[i]);

	}

	sort(tmp.begin(),tmp.end());reverse(tmp.begin(),tmp.end());//从大到小地取区间最小值

	int L=mid,R=mid+1;

	ans=max(ans,answ(L,R,query(L,R)));

	for(int i=0;i<tmp.size();i++){//由于最小值“逐渐放宽”，所以区间只增不减

		if(tmp[i]>a[mid]||tmp[i]>a[mid]){

			continue;

		}

		while(a[L-1]>=tmp[i]&&L!=l){

			L--;

		}

		while(a[R+1]>=tmp[i]&&R!=r){

			R++;

		}//区间越大越好

		ans=max(ans,answ(L,R,query(L,R)));

	}

	return ans;

}

int main(){

    cin>>n;

    for(int i=1;i<=n;i++){

    	cin>>a[i];

    	sum[i]=sum[i-1]+a[i];

    }

    qwq.build();

    answ ans=dfs(1,n);

    cout<<ans.v<<endl;

    cout<<ans.l<<" "<<ans.r<<endl;

    return 0;

}

巴特西

UVA1619 感觉不错 Feel Good（良好的感觉）题解

0.题面：

1.思路

2.Code

最新文章

热门文章

巴特西

UVA1619 感觉不错 Feel Good（良好的感觉） 题解

0.题面：

1.思路

2.Code

最新文章

热门文章

UVA1619 感觉不错 Feel Good（良好的感觉）题解