首页 > 代码库 > Codeforces 727 F. Polycarp's problems

Codeforces 727 F. Polycarp's problems

2024-08-19 23:35:37   213人阅读

Description

有一个长度为 \(n\) 有正负权值的序列,你一开始有一个值,每次到一个权值就加上,最少需要删掉多少数值才能到序列末尾.\(n \leqslant 750,m \leqslant 2 \times 10^5\)

Sol

DP+二分.

发现这个东西有后效性,就是前面选不选会影响后面的决策,并且权值太大无法记录.

但是我们可以倒着做,因为后面的决策无法影响前面的决策.

\(f[i][j]\) 表示到 \(i\) 删掉 \(j\) 个至少需要的初始权值.

因为初始权值非负,所以不可能在中途中出现负数,要处理掉,然后就两个决策,删或不删,转移就很好写了.

统计答案的时候他有单调性,可以二分.

Code

#include<cstdio>#include<cstring>#include<iostream>using namespace std;typedef long long LL;const int N = 755;int n,m;LL a[N],f[N][N],w[N];inline LL in(LL x=0,char ch=getchar()){ while(ch>‘9‘||ch<‘0‘) ch=getchar();	while(ch>=‘0‘ && ch<=‘9‘) x=(x<<3)+(x<<1)+ch-‘0‘,ch=getchar();return x; }void work(LL x){	int l=0,r=n,mid;	while(l<=r){		mid=(l+r)>>1;		if(f[1][mid] <= x) r=mid-1;		else l=mid+1;	}printf("%d\n",l);}int main(){		scanf("%d%d",&n,&m);	for(int i=1;i<=n;i++) cin>>a[i];		memset(f,0x3f,sizeof(f));	f[n+1][0]=0LL;	for(int i=n;i;i--) for(int j=0;j<n-i+1;j++){		f[i][j]=min(f[i][j],max(0LL,f[i+1][j]-a[i]));		f[i][j+1]=min(f[i][j+1],f[i+1][j]);	}		for(;m--;) work(in());	return 0;}

　　

Codeforces 727 F. Polycarp's problems


联系
我们