CF练习题17(DP)

Chocolate Bar

我们看到 \(n,m\le 30\) 想到暴搜。

考虑枚举分割线，一直到刚好满足需要或者只有一个巧克力的情况。

随手跑了个最优解。

inline int dfs(int n,int m,int k){
	if(n*m==k)return 0;
	if(k<=0)return 0;
	if(f[n][m][k]<inf)return f[n][m][k];
	int res=inf;
	up(i,1,m){
		if(m-i<=0)break;
		res=min(res,dfs(n,i,min(i*n,k))+dfs(n,m-i,max(k-i*n,0))+n*n);
	}
	up(i,1,n){
		if(n-i<=0)break;
		res=min(res,dfs(i,m,min(i*m,k))+dfs(n-i,m,max(k-i*m,0))+m*m);
	}
	return f[n][m][k]=res;
}
int n,m,k;
signed main() {
	T=read();
	memset(f,0x3f,sizeof f);
	while(T--){
		n=read();m=read();k=read();
		write(dfs(n,m,k),1);
	}
	return 0;
}

Hard Process

显然，答案具有单调性，所以可以考虑直接二分。

int n,k,sum[N],a[N];
int ans=0,p=0;
signed main(){
    n=read();k=read();
    up(i,1,n){
        a[i]=read();
        sum[i]=sum[i-1]+(a[i]==0);
    }
    up(i,1,n){
        int l=i,r=n,maxl=0;
        while(l<=r){
            int mid=(l+r)>>1;
            if(sum[mid]-sum[i-1]<=k){
                l=mid+1;
                maxl=mid-i+1;
            }
            else r=mid-1;
        }
        if(ans<maxl)ans=maxl,p=i;
    }
    write(ans,1);
    up(i,1,n){
        if(i>=p&&i<=p+ans-1)write(1,0);
        else write(a[i],0);
    }
    return 0;
}