HDU4281 Judges' response（狀態壓縮+01背包+分組背包）經典
Judges' response
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 565 Accepted Submission(s): 308
Problem Description
The contest is running and the judges is busy watching the progress of the contest. Suddenly, N - 1 (N <= 16) contestants hand up their hand at the same time. The judges should go to answer the contestants' question one by one.
The judges already foresee that answering contest i's question would cost Ci minutes. In order to serve all the contestant, each judges is assigned to serve some subset of the contestants. As the judges have limited patience, each one of them can serve the
contestants for no more than M minutes.
You are asked to solve two problems:
1. At least how many judges should be sent so that they can serve all the contestants? (Because the judges have limited patience, each one of them cannot serve too many contestants.)
2. If there are infinite number of judges, how to assign the route for each judge so that the sum of their walking time is minimized? Each contestant i is reside in place (xi, yi), the judges are in place (x1, y1). Assuming
the walking speed of the judge is 1.
Input
There are several test cases, Each case begin with two integer N, M(with the meaning in the above context, 2 <= N <= 16, 0 <= M <= 100000).
Then N lines follow and line i will contain two numbers x, y(0 <= x, y <= 1000), indicating the coordinate of place i.
Then another N lines follow and line i will contain numbers Ci(0 <= Ci <= 1000), indicating the time to solve contestant i's question. C1 will 0 as place 1 is for the judges.
The distance between place i and place j is defined as ceil(sqrt((xi - xj) ^ 2 + (yi - yj) ^ 2)). (ceil means rounding the number up, e.g. ceil(4.1) = 5)
Output
For each case, output two numbers. The first is the minimum number of judges for question 1. The second is the minimum sum of walking time for question 2.
If it's impossible to serve all the contestants, please output -1 -1 instead.
Sample Input
3 3
0 0
0 3
0 1
0
1
2
3 2
0 0
0 3
0 1
0
1
2
3 1
0 0
0 3
0 1
0
1
2
16 35
30 40
37 52
49 49
52 64
31 62
52 33
42 41
52 41
57 58
62 42
42 57
27 68
43 67
58 48
58 27
37 69
0
19
30
16
23
11
31
15
28
8
8
7
14
6
19
11
Sample Output
1 6
2 8
-1 -1
8 467
Source
2012 ACM/ICPC Asia Regional Tianjin Online
題意：給出n個點，第一個點是裁判的位置，其余n-1個點是任務需要裁判去完成，每個裁判去完成任務總時間不能超過M（不包括走路的時間） ，每個點都有一個坐標和完成這個任務的時間，裁判從一個點到另一個時間所花的時間是兩點之間的距離，（1）求完成所有任務最少需要多少個裁判。（2）如果有無數個裁判，要求完成所有的任務所經路程的時間總和最小是多少。（每個裁判最終要回到原來的位置，且最少用到條件（1）得到的裁判個數）。
分析：因為每個裁判做任務總時間不能超過M ，所以用狀態壓縮把一個裁判能完成的任務找出來，並且記錄下來，那麼接下來完成第（1）問就好辦了，直接DP一下。要想做出第（2）問，那麼首先要算出一個裁判去完成的任務狀態（必須這種狀態一個裁判能完成）的最少用時（不包括返回原來位置的用時），之後再把每個狀態以某個點作為結尾點返回到裁判原來的位置的最少用時。再用一個分組背包求出用i 個裁判去完成任務狀態 s 花的最少時間，最後就得出結果。
#include
#include
const int N = 1<<16 ;
const int inf= 0xfffffff ;
int dpk[N],dps[N],state[N],k,ok[N];
int map[16][16],routeDist[N][16],dpks[16][N];
double x[16],y[16];
int n,M,c[16];
//------------初始化-------------
void init()
{
//求出兩點之間這距離
for(int i=0; ib?b:a;}
void countRouteDist()
{
int tn=n-1;
for(int i=1; i<(1<state[j]; s--) //每種任務的狀態
if((s|state[j])==s&&dpks[i-1][s^state[j]]!=inf)
dpks[i][s]=min(dpks[i][s],dpks[i-1][s^state[j]]+dps[state[j]]);
}
void zeroOne()
{
int tn=n-1;
for(int i=0; i=state[i]; s--)
if((s|state[i])==s)
{
if(dpk[s]>dpk[s^state[i]]+1)
dpk[s]=dpk[s^state[i]]+1;
}
}
int main()
{
int flag,MIN;
while(scanf("%d%d",&n,&M)>0)
{
flag=0;
scanf("%lf%lf",&x[n-1],&y[n-1]);//裁判的位置
for(int i=0; iM) flag=1;
}
if(flag)
{
printf("-1 -1\n"); continue;
}
init();
zeroOne();
countRouteDist();
n--;
MIN=inf;
for(int i=dpk[(1<
