cf1175 D\E

链接

成功带wxy掉分、、全程0输出

D

E

D 题意

把序列分成连续k段，f(i)表示i这个在第几段

\(\sum\limits_{i=1}^{n}a_i*f(i)\)最大

思路

想象成从k层积木依次递减

先把积木搭满，也就是\(sum_n*k\)

然后考虑删除积木，删除k-1个最小的前缀和就行。

sum[n]不能加进去

代码

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N=3e5+7;

int n,k;

ll sum[N];

int main() {

	scanf("%d%d",&n,&k);

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

		scanf("%d",&val);

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

	}

	ll ans=k*sum[n];

	sort(sum+1,sum+n);

	for(int i=1;i<k;++i) ans-=sum[i];

	cout<<ans<<"\n";

	return 0;

}

E 题意

多次询问求一条线段最少被多少线段覆盖

思路

倍增

f[i][j]表示从第i个点出发，用\(2^j\)条线段最多到哪里，

注意从0开始

代码

#include <bits/stdc++.h>

using namespace std;

const int N=5e5+7;

int n,m,f[N][21],bj;

int main() {

	scanf("%d%d",&n,&m);

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

		int x,y;

		scanf("%d%d",&x,&y);

		f[x][0]=max(f[x][0],y);

		bj=max(bj,y);

	}

	for(int i=1;i<=bj;++i) f[i][0]=max(f[i-1][0],f[i][0]);

	for(int j=1;j<=20;++j)

		for(int i=0;i<=bj;++i)

			f[i][j]=f[f[i][j-1]][j-1];

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

		int ans=0,x,y;

		scanf("%d%d",&x,&y);

		for(int i=20;i>=0;--i)

			if(f[x][i]<y)

				ans+=1<<i,x=f[x][i];

		printf("%d\n",f[x][0]>=y?ans+1:-1);

	}

	return 0;

}

巴特西

cf1175 D\E

链接

D 题意

思路

代码

E 题意

思路

代码

最新文章

热门文章