題目：給出N個人，其中0號是裁判的位置，剩下有N-1的人提問，裁判需要去回答問題，每個人有一個val，每個裁判能拿到的val的上限為K。問題最少需要幾個裁判，以及最少時間
第一問可以狀態壓縮DP解決，dp[i]表示狀態i需要幾個裁判，也可以排序之後貪心。從大到小，盡可能地裝入一個盒子。
第二問就是多個TSP問題，dp[i][j]表示當前位置 在i，可行狀態為j的最小費用，best[i]表示對於狀態i的最小費用（而且是一個完整狀態，裁判都回到原點），因為之前TSP中是求的可行狀態，也就是每個裁判的上限不能超過K。之後就是枚舉所有狀態，對於一個狀態，枚舉他的所有子集，見代碼中的位運算部分。而且兩個子集中必須要包含0號結點，因為每個裁判都是從0出發的
[cpp]
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#define inf 1<<28
#define M 100005
#define N 55
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define pb(a) push_back(a)
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define MOD 1000000007
using namespace std;
struct Point{
int x,y;
}p[20];
int n,m,val[20],path[20][20];
int dp[16][1<<16];
int best[1<<16],ok[1<<16];
int dist(Point p1,Point p2){
return ceil(sqrt((double)(p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)));
}
void Get_dist(){
for(int i=0;i<n;i++) for(int j=0;j<n;j++) path[i][j]=dist(p[i],p[j]);
}
void Init(){
for(int i=0;i<n;i++)
for(int j=0;j<(1<<n);j++)
dp[i][j]=inf;
for(int i=0;i<(1<<n);i++)
best[i]=inf;
dp[0][1]=0;
}
int check(int state){
int sum=0;
for(int i=0;i<n;i++)
if(state&(1<<i))
sum+=val[i];
return sum<=m;
}
bool cmp(int a,int b){return a>b;}
int slove(){
int v[20];
memcpy(v,val,sizeof(val));
sort(v,v+n,cmp);
if(v[0]>m) return -1;
int flag[20];
mem(flag,0);
int cnt=0;
for(int i=0;i<n;i++){
if(flag[i]) continue;
int tmp=0;
for(int j=i;j<n;j++){
if(flag[j]==0){
if(tmp+v[j]<=m){
flag[j]=1;
tmp+=v[j];
}
}
}
cnt++;
}
return cnt;
}
int TSP(){
for(int i=0;i<(1<<n);i++){
if(ok[i])
for(int j=0;j<n;j++)
if(i&(1<<j)){
best[i]=min(best[i],dp[j][i]+path[j][0]);
for(int k=0;k<n;k++)
if(!(i&(1<<k)))
dp[k][i|(1<<k)]=min(dp[k][i|(1<<k)],dp[j][i]+path[j][k]);
}
}
for(int i=0;i<(1<<n);i++)
if(i&1)
for(int j=i&(i-1);j;j=i&(j-1))
best[i]=min(best[i],best[j]+best[(i-j)|1]);
return best[(1<<n)-1];
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=0;i<n;i++) scanf("%d%d",&p[i].x,&p[i].y);
for(int i=0;i<n;i++) scanf("%d",&val[i]);
for(int i=0;i<(1<<n);i++) ok[i]=check(i);
Get_dist();
Init();
int ans1=slove();
if(ans1==-1) {printf("-1 -1\n");continue;}
printf("%d %d\n",ans1,TSP());
}
return 0;
}
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#define inf 1<<28
#define M 100005
#define N 55
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define pb(a) push_back(a)
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define MOD 1000000007
using namespace std;
struct Point{
int x,y;
}p[20];
int n,m,val[20],path[20][20];
int dp[16][1<<16];
int best[1<<16],ok[1<<16];
int dist(Point p1,Point p2){
return ceil(sqrt((double)(p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)));
}
void Get_dist(){
for(int i=0;i<n;i++) for(int j=0;j<n;j++) path[i][j]=dist(p[i],p[j]);
}
void Init(){
for(int i=0;i<n;i++)
for(int j=0;j<(1<<n);j++)
dp[i][j]=inf;
for(int i=0;i<(1<<n);i++)
best[i]=inf;
dp[0][1]=0;
}
int check(int state){
int sum=0;
for(int i=0;i<n;i++)
if(state&(1<<i))
sum+=val[i];
return sum<=m;
}
bool cmp(int a,int b){return a>b;}
int slove(){
int v[20];
memcpy(v,val,sizeof(val));
sort(v,v+n,cmp);
if(v[0]>m) return -1;
int flag[20];
mem(flag,0);
int cnt=0;
for(int i=0;i<n;i++){
if(flag[i]) continue;
int tmp=0;
for(int j=i;j<n;j++){
if(flag[j]==0){
if(tmp+v[j]<=m){
flag[j]=1;
tmp+=v[j];
}
}
}
cnt++;
}
return cnt;
}
int TSP(){
for(int i=0;i<(1<<n);i++){
if(ok[i])
for(int j=0;j<n;j++)
if(i&(1<<j)){
best[i]=min(best[i],dp[j][i]+path[j][0]);
for(int k=0;k<n;k++)
if(!(i&(1<<k)))
dp[k][i|(1<<k)]=min(dp[k][i|(1<<k)],dp[j][i]+path[j][k]);
}
}
for(int i=0;i<(1<<n);i++)
if(i&1) www.2cto.com
for(int j=i&(i-1);j;j=i&(j-1))
best[i]=min(best[i],best[j]+best[(i-j)|1]);
return best[(1<<n)-1];
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=0;i<n;i++) scanf("%d%d",&p[i].x,&p[i].y);
for(int i=0;i<n;i++) scanf("%d",&val[i]);
for(int i=0;i<(1<<n);i++) ok[i]=check(i);
Get_dist();
Init();
int ans1=slove();
if(ans1==-1) {printf("-1 -1\n");continue;}
printf("%d %d\n",ans1,TSP());
}
return 0;
}
