这道题要将序列分为一个或多个连续序列,且要求每个序列的和相等,找到可能成功划分的最小厚度。
因为要求每个序列的和相等,所以总数除以序列的值一定可以整除,所以就依据这个不断的枚举序列长度,并通过dfs进行验证,直到找到最符合题意的长度。
#include<bits/stdc++.h>
using namespace std;
const int M=2005;
int a[M];
int sum;
bool dfs(int n,int base,int pos,int &len){
int s=0; int length=0;
for(int i=pos;i<=n;i++){
s+=a[i];
++length;
if(s>base) return false;
if(s==base){
len=max(len,length);
if(i==n) return true;
if(dfs(n,base,i+1,len)) return true;
}
}
return false;
}
int main(){
int t; cin>>t;
while(t--){
int n; cin>>n;
sum=0;
for(int i=1;i<=n;i++){
cin>>a[i];
sum+=a[i];
}
int s=0; int ans=1e4+5;
for(int i=1;i<=n;i++){
s+=a[i];
if(i==n){
ans=min(ans,n);
break;
}
if(sum%s==0){
int length=i;
if(dfs(n,s,i+1,length)){
ans=min(ans,length);
}
}
}
cout<<ans<<'\n';
}
}