HDU6606 Distribution of books 2019 항저우 다교 3차전

시험장에서 2분 후에 욕심만 냈을 뿐 DP는 생각하지 않았다
문제풀이 속의 DP를 보고 1초 만에 생각해 냈더니 웅덩이에 물이 차서 물문제를 끝내도 풀지 못했다.
답을 고려한 다음에 dp[i]는 분배 전 i권의 책을 최대 몇 명에게 나누어 줄 수 있음을 나타낸다. 그리고 i로 끝낼 수 없으면 dp수 그룹을 업데이트하지 않는다.
그리고 접두사와 이산화, dp[i]=max(dp[j]+1),sum[i]-sum[j]<=mid,그러면sum[j]>=sum[i]-mid로 가장 작은 이산화값을 나누고, 권한 트리 수조는 표시된sum[j]가 얻을 수 있는 최대 dp[j]를 유지한다.그리고 이전 i개를 완전히 분배해야 하기 때문에 반드시 풀이가 있어야 dp[i]와 권한 트리 그룹을 업데이트할 수 있습니다

#include
using namespace std;
#define maxl 200010


int n,tot,cnt,k;
long long up,dow,ans;
int a[maxl],b[maxl],dp[maxl],h[maxl],c[maxl];
long long sum[maxl];
long long num[maxl];


inline void prework()
{
	scanf("%d%d",&n,&k);
	up=0;dow=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		sum[i]=sum[i-1]+a[i],num[i]=sum[i];
		if(a[i]>0) up+=a[i];
		else dow+=a[i];
	}
	num[n+1]=0;
	sort(num+1,num+2+n);
	tot=unique(num+1,num+2+n)-num-1;
	for(int i=0;i<=n;i++)
		b[i]=lower_bound(num+1,num+1+tot,sum[i])-num;
}

inline void upd(int i,int x) 
{
	int t;
	while(i<=tot && i)
	{
		h[i]=c[i];
		for(int k=1;ktot)
			continue;
		tmp=qry(id,tot);
		if(tmp<=-n-1)
			continue;
		dp[i]=max(dp[i],qry(id,tot)+1);
		c[b[i]]=max(c[b[i]],dp[i]);
		upd(b[i],c[b[i]]);
		if(dp[i]>=k)
			return true;
	}
		return false;
}

inline void mainwork()
{
	long long l=dow,r=up,mid;
	while(l+1>1;
		if(jug(mid))
			r=mid;
		else
			l=mid;
	}
	if(jug(l))
		ans=l;
	else
		ans=l+1;
}

inline void print()
{
	printf("%lld
",ans);
}

int main()
{
	int t;
	scanf("%d",&t);
	for(int i=1;i<=t;i++)
	{
		prework();
		mainwork();
		print();
	}
	return 0;
}