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;
}