19-0604算法总结

Author Avatar
Xzhah 6月 04, 2019
  • 在其它设备中阅读本文章

[TOC]

1166-C

没啥好说的，二分法函数lower_bound和upper_bound要会用。在algorithm里

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;

int main(){
	ll a[200001]={0};
	int n;
	cin>>n;
	for(int i=1;i<=n;++i)
	{cin>>a[i];
	a[i]=abs(a[i]);
	}
	sort(a+1,a+1+n);
	ll sum=0;
	for(int i=1;i<n;++i)
		sum+=((upper_bound(a+i,a+1+n,2*a[i])-a)-i-1);
	cout<<sum<<endl;



}

1155-D

动态规划是给人做的嗷？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

int main(){
	int n,x;
	cin>>n>>x;
	ll a[300001]={0};
	ll dp[3][300001]={0};
	for(int i=1;i<=n;++i)
		cin>>a[i];
	ll res=0;
	//首先找出都没乘以x的最大子组
	for(int i=1;i<=n;++i)
	{
		dp[0][i]=a[i]+max(dp[0][i-1],(ll)0);//只要前面和是正数就可以加上，dp[0][i]表示该连续子组一定是a[i]结尾，且为其算上a[i]和的最大值。
		res=max(res,dp[0][i]);
	}
	//然后是找以a[i]结尾，且a[i]乘了x的子组
	for(int i=1;i<=n;++i)
	{
		dp[1][i]=a[i]*x+max(max(dp[1][i-1],dp[0][i-1]),(ll)0);//也就是说乘以x要么从当前开始，要么加上上一个也乘了x的子组最大，要么前面都没乘。
		res=max(res,dp[1][i]);
	}
	//最后是a[i]没乘，前面乘了的情况
	if(n>1)
		dp[2][2]=a[2]+a[1]*x;//这种情况至少从a[2]开始
	res=max(res,dp[2][2]);
	for(int i=3;i<=n;++i)
	{
		dp[2][i]=a[i]+max(dp[2][i-1],dp[1][i-1]);
		res=max(res,dp[2][i]);
	}
	cout<<res<<endl;
	return 0;
}