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;
}