Judges' response
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 678 Accepted Submission(s): 389
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
Recommend liuyiding | We have carefully selected several similar problems for you: 4267 4268 4269 4270 4271
两个问题，一个是状态压缩DP，一个是经典的旅行商问题。
代码中的solve_second中第一个三重循环实际上是初始化np，
第二个二重循环才是递推求出np。
集合x是s的子集： s==x|s , x==x&s
集合x与s的有交集: x&s
对于集合s，求它的所有非空真子集: for(int x=(s-1)&s ; x ;x=(x-1)&s ) { }
很方便修改为子集。
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<climits>
#include<queue>
#include<vector>
#include<map>
#include<sstream>
#include<set>
#include<stack>
#include<cctype>
#include<utility>
#pragma comment(linker, "/STACK:102400000,102400000")
#define PI (4.0*atan(1.0))
#define eps 1e-10
#define sqr(x) ((x)*(x))
#define FOR0(i,n) for(int i=0 ;i<(n) ;i++)
#define FOR1(i,n) for(int i=1 ;i<=(n) ;i++)
#define FORD(i,n) for(int i=(n) ;i>=0 ;i--)
#define lson ind<<1,le,mid
#define rson ind<<1|1,mid+1,ri
#define MID int mid=(le+ri)>>1
#define zero(x)((x>0? x:-x)<1e-15)
#define mk make_pair
#define _f first
#define _s second
#define ysk(x) (1<<(x) )
using namespace std;
//const int INF= ;
typedef long long ll;
//const ll inf =1000000000000000;//1e15;
//ifstream fin("input.txt");
//ofstream fout("output.txt");
//fin.close();
//fout.close();
//freopen("a.in","r",stdin);
//freopen("a.out","w",stdout);
const int INF =0x3f3f3f3f;
const int maxn= 20 ;
const int N= 16 ;
const int maxV= ysk(N+1);
//const int maxm= ;
int n,V,st,ed;
vector<int >ve;
int dp[maxV];
int time[maxn];
struct POS
{
int x,y;
} pos[maxn];
int dis[maxn][maxn];
int np[maxV];//np[ed]即为第二问答案
int cost[maxV][maxn];//状态 终点
bool vis[maxV];
int getdis(int i,int j)
{
int d1=pos[i].x-pos[j].x;
int d2=pos[i].y-pos[j].y;
return ceil(sqrt( sqr(d1)+sqr(d2) ) );
}
void pre()
{
FOR0(i,n)
{
FOR0(j,n)
{
dis[i][j]=getdis(i,j);
}
}
ed=ysk(n)-1;
ve.clear();
memset(vis,0,sizeof vis);
for(int i=1;i<=ed;i++)
{
int ret=0;
for(int j=0;j<n;j++)
{
if(i&ysk(j)) ret+=time[j];
}
if(ret>V) continue;
vis[i]=1;
ve.push_back(i);
}
}
void solve_first()
{
memset(dp,0x3f, (ed+1) *sizeof dp[0] );
dp[1]=0;
for(int s=1;s<=ed;s++)
{
for(int i=0;i<ve.size();i++)
{
int x=ve[i];
if( x&s ) continue;
dp[x|s]=min(dp[x|s],dp[s]+1 );
}
}
}
void solve_second()
{
memset(np,0x3f,(ed+1)*sizeof np[0]);
memset(cost,0x3f, sizeof cost);
cost[1][0]=0;
for(int s=1;s<=ed;s++) if(vis[s])
{
for(int i=0;i<n;i++) if(s&ysk(i))
{
np[s]=min(np[s], cost[s][i] +dis[i][0] );
for(int j=0;j<n;j++) if( s!= (s| ysk(j) ) )
{
cost[s|ysk(j)][j]=min(cost[s|ysk(j)][j] ,cost[s][i]+dis[i][j] );
}
}
}
for(int s=1;s<=ed;s++) if(s&1)
{
for(int i=(s-1)&s ; i ;i=(i-1)&s )//for(int i=(s-1)&s ; i ;i=(i-1)&i ) ¸ÃËÀ£¬´òÁ³
{
np[s] =min(np[s],np[i|1]+np[ (s^i)|1 ] );
}
}
}
int main()
{
while(~scanf("%d%d",&n,&V))
{
FOR0(i,n) scanf("%d%d",&pos[i].x,&pos[i].y);
bool ok=1;
FOR0(i,n)
{
scanf("%d",&time[i]);
if(time[i]>V) ok=0;
}
if(!ok) { puts("-1 -1"); continue;}
pre();
solve_first();
printf("%d ",dp[ed]);
solve_second();
printf("%d\n",np[ed]);
}
return 0;
}
代码中最后解决的那个TSP问题，不仅初始化与一般dp不一样，而且对于集合s，划分为好几个子集x之并集，而且每个并集都要求包含1<<0（只有这个元素相同），这一技巧值得琢磨。
![【半年时光-追寻你的足迹】[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)