Project Euler 222 Sphere Packing

开启传送门

题目描述

What is the length of the shortest pipe, of internal radius $50$mm, that can fully contain $21$ balls of radii $30$mm, $31$mm, …, $50$mm?

Give your answer in micrometres ($10^{-6}$ m) rounded to the nearest integer.

题意

让你在一个内径$50$的圆管里塞$21$个内径分别为$31-50$的小球,问你圆管最短是多少

分析

比较显然是dp

考虑dp状态:dp[i][j]表示选择小球对应的集合为j,并且用第i个小球结尾,然后我们转移的时候就直接添加一个小球,对于剩余的小球枚举一个结尾,取最优解就行了

代码

给大佬递上我奇丑无比的代码 (/ω\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;
const int maxm = 21;
double ans[maxm][1<<maxm];
int num[maxm+10];
double cal(int a,int b){//得到两个小球的距离
int t = a+b+60;
return 10*sqrt(t*2-100);
}
int main(){
for(int i = 0;i<maxm;i++) for(int j = 0;j<(1<<maxm);j++) ans[i][j] = 1e8;
for(int s = 0;s<(1<<maxm);s++) for(int i = 0;i<maxm;i++){
if(s==0){//初值条件
ans[i][1<<i] = i+30;
continue;
}
if((s >> i & 1)==1) continue;
int t = s|(1<<i);//用S来扩展t
for(int j = 0;j<maxm;j++) if(s>>j&1) ans[i][t] = min(ans[i][t],ans[j][s]+cal(i,j));
}
double rans = 1e8;
for(int i = 0;i<maxm;i++) rans = min(rans,ans[i][(1<<maxm)-1]+i+30);
printf("%.0f\n",rans*1000);
return 0;
}