网站源码交易网,乐趣做网站,电子商务建设网站,网站开发三步CF332B CF332B
暴力思路
题目要我们找两个不重叠的区间#xff0c;并使区间的值最大。那我们可以考虑使用双重循环搭配前缀和暴力求最大值。代码如下。
for(int i1;in;i)
{ll lsum[ik-1]-sum[i-1],maxx;for(int jik;jn;j){maxxlsum[jk-1]-sum[j-1];if(maxxans.…CF332B CF332B
暴力思路
题目要我们找两个不重叠的区间并使区间的值最大。那我们可以考虑使用双重循环搭配前缀和暴力求最大值。代码如下。
for(int i1;in;i)
{ll lsum[ik-1]-sum[i-1],maxx;for(int jik;jn;j){maxxlsum[jk-1]-sum[j-1];if(maxxans.sum){ans.xi;ans.yj;ans.summaxx;}}
}但是暴力的时间复杂度是一定会超时的。那我们考虑一下优化。
优化思路
我们可以思考一下如何把第二层循环给优化掉。我们可以用一个结构体数组 m a x x [ i ] maxx[i] maxx[i] 来记录 i ∼ n i \sim n i∼n 的最大的区间值并记录这个区间的起点。这样我们就把第二层循环给优化掉了。
最重要的注意数据范围要开 long long。
代码
#includebits/stdc.h
#includecstring
#includequeue
#includeset
#includestack
#includevector
#includemap
#define ll unsigned long long
#define lhs printf(\n);
using namespace std;
const int N3e510;
const int M2024;
const int inf0x3f3f3f3f;
ll n,k;
ll a[N];
ll sum[N];
struct node
{ll num;int id;
}maxx[N];
struct nodee
{ll sum;ll x,y;
}ans;
int main()
{scanf(%lld%lld,n,k);for(int i1;in;i){scanf(%lld,a[i]);sum[i]sum[i-1]a[i];//前缀和} for(int in;i1;i--){if(ik-1n)continue;ll lsum[ik-1]-sum[i-1];//更新最大值if(maxx[i1].numl){maxx[i].nummaxx[i1].num;maxx[i].idmaxx[i1].id;}else{maxx[i].numl;maxx[i].idi;}} for(int i1;in;i){if(ik-1n)continue;ll lsum[ik-1]-sum[i-1];ll rmaxx[ik].num,ridmaxx[ik].id;if(lrans.sum){ans.xi;ans.yrid;ans.sumrl;}} printf(%lld %lld,ans.x,ans.y);return 0;
}
