AT ABC203F

AK留念

Lemma

由于每次\(h_{max}\)都会递减至原来的\(\dfrac{1}{2}\),所以操作数最多不超过\(log_2 h_{max}\)

Solve

显然先按h大小排序
一个比较精巧的思路，转化\(dp\)数组的权值与下标
正常的\(dp\):\(dp[i][j]\)表示删除了前\(i\)小的杂草，提前拔了\(j\)颗草最少用的步数
由于\(dp\)权值极小，同时提前拔草数也满足\(dp\)的性质，转化两位
转化后的\(dp\):\(dp[i][j]\)表示删除了前\(i\)小的杂草，操作了j次，提前拔草的最少数量
\(dp\)转移极为简单，这不，这不有手就行

代码环节

#include<bits/stdc++.h>
using namespace std;
 
#define Mod(x) (x>=P)&&(x-=P)
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
#define erep(i,a) for(int i=hd[a];i;i=nxt[i])
 
typedef long long ll;
void Max(int &x,int y){(x<y)&&(x=y);}
void Min(int &x,int y){(x>y)&&(x=y);}
 
bool vio;
char IO;
int rd(int res=0){
	bool f=0;
	while(IO=getchar(),IO<48||IO>57)
		f=IO==‘-‘;
	do res=(res<<1)+(res<<3)+(IO^48);
	while(IO=getchar(),isdigit(IO));
	return f?-res:res;
}
const int M=2e5+10;
int dp[M][33],A[M];
bool let;
int main(){
	cerr<<(&vio-&let)/1024.0/1024<<endl;
	int n=rd(),K=rd();
	rep(i,1,n)A[i]=rd();
	sort(A+1,A+n+1);
	rep(i,1,n){
		rep(j,0,30)dp[i][j]=dp[i-1][j]+1;
		int ps=upper_bound(A+1,A+n+1,A[i]/2)-A-1;
		rep(j,1,30)Min(dp[i][j],dp[ps][j-1]);
	}
	rep(i,0,30)if(dp[n][i]<=K){
		printf("%d %d",i,dp[n][i]);
		return 0;
	}
}

AT ABC203F

原文：https://www.cnblogs.com/Saltywater/p/14854691.html