设为首页 加入收藏

TOP

HDU 4281 Judges' response（12年天津 MTSP问题） (一)
2015-11-21 01:05:54 来源: 作者: 【大 中 小】 浏览:9次
Tags：HDU 4281 Judges' response 12年 天津 MTSP 问题

题目：给出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??
#include??
#include??
#include??
#include??
#include??
#include??
#include??
#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 }?
void Init(){?
??? for(int i=0;i ??????? for(int j=0;j<(1< ??????????? dp[i][j]=inf;?
??? for(int i=0;i<(1< ??????? best[i]=inf;?
??? dp[0][1]=0;?
}?
int check(int state){?
??? int sum=0;?
??? for(int i=0;i ??????? if(state&(1< ??????????? 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 ??????? if(flag[i]) continue;?
??????? int tmp=0;???
??????? for(int j=i;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< ??????? if(ok[i])?
??????????? for(int j=0;j ??????????????? if(i&(1< ??????????????????? best[i]=min(best[i],dp[j][i]+path[j][0]);?
??????????????????? for(int k=0;k ??????????????????????? if(!(i&(1< ??????????????????????????? dp[k][i|(1< ??????????????? }?
??? }?
??? for(int i=0;i<(1< ??????? 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< }?
?
int main(){?
??? while(scanf("%d%d",&n,&m)!=EOF){?
??????? for(int i=0;i ??????? for(int i=0;i ??????? for(int i=0;i<(1< ??????? Get_dist();?
??????? Init();?
??????? int ans1=slove();?
??????? if(ans1==-1) {printf("-1 -1\n");continue;}?
??????? printf("%d %d\n",ans1,TSP());?
??? }?
??? return 0;?
}?

#include
#include
#include
#include
#include
#include
#include
#include
#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 }
void Init(){
?for(int i=0;i ??for(int j=0;j<(1< ???dp[i][j]=inf;
?for(int i=0;i<(1< ??best[i]=inf;
?dp[0][1]=0;
}
int check(int state){
?int sum=0;
?for(int i=0;i ??if(state&(1< ???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
首页 上一页 1 2 下一页 尾页 1/2/2
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：poj 2822 & hdu 4280 <平面图.. 下一篇：Hdu 4281 Judges' response (..

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: