2169. Baking Cakes

二分 + 贪心 能不能破 ？

include

include

include

include

using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 45;
int a[maxn];
bool v[maxn];
int pre[maxn];
int dp[1300];
bool cv[1300];
int n;
bool judge(int k){
memset(v,false,sizeof(v));
for(int p = 1;p <= 3;p ++){
memset(dp,0,sizeof(dp));
memset(pre,-1,sizeof(pre));
memset(cv,false,sizeof(cv));
cv[0] = true;
for(int i = 0;i < n;i ++){
if(!v[i]){
for(int j = k;j >= a[i];j –){
if(cv[j - a[i]]){
//printf(“vj = %d\n”,j);
if(dp[j] < dp[j - a[i]] + a[i]){
dp[j] = dp[j - a[i]] + a[i];
pre[j] = j - a[i];
cv[j] = true;
}
}
}
}
}
int tk;
for(tk = k;!cv[tk];tk –);
//printf(“tk = %d\n”,tk);
for(int j = tk;j != 0;j = pre[j]){
//printf(“j = %d pre = %d\n”,j,pre[j]);
for(int q = 0;q < n;q ++){
if(!v[q] && a[q] == j - pre[j]){
v[q] = true;
break;
}
}
}
}
for(int i = 0;i < n;i ++){
if(!v[i])return false;
}
return true;
}
int main(){
while(scanf(“%d”,&n) && n){
for(int i = 0;i < n;i ++){
scanf(“%d”,&a[i]);
}
int l = 1;
int r = 1300;
while(l <= r){
int mid = (l + r)>>1;
//printf(“l = %d r = %d mid = %d\n”,l,r,mid);
if(judge(mid))r = mid - 1;
else l = mid + 1;
}
printf(“%d\n”,l);
}
return 0;
}