T1:升降梯
Problem:
Nescafe 之塔一共有 N 层，升降梯在每层都有一个停靠点。手柄有 M 个控制槽，第 i 个控制槽旁边标着一个数 Ci，满足 C1<C2<C3<……<CM。如果 Ci>0，表示手柄扳动到该槽时，电梯将上升 Ci 层；如果 Ci<0，表示手柄扳动到该槽时，电梯将下降-Ci 层；并且一定存在一个 Ci=0，手柄最初就位于此槽中。注意升降梯只能在 1~N 层间移动，因此扳动到使升降梯移动到 1 层以下、N 层以上的控制槽是不允许的。
电梯每移动一层，需要花费 2 秒钟时间，而手柄从一个控制槽扳到相邻的槽，需要花费 1 秒钟时间。探险队员现在在 1 层，并且想尽快到达 N 层，他们想知道从 1 层到 N 层至少需要多长时间？
Code:
1 #include<bits/stdc++.h>
2 using namespace std;
3 int st,c[30];
4 int n,m;
5 int dis[1010][30];
6 bool vis[1010][30];
7 struct node{int x,y;};
8 queue<node> q;
9 int ans=1919810;
10 void spfa(int x){
11 memset(dis,0x3f,sizeof(dis));
12 node tmp;
13 tmp.x=1,tmp.y=x;
14 vis[1][x]=1;
15 dis[1][x]=0;
16 q.push(tmp);
17 while(!q.empty()){
18 node now=q.front();
19 q.pop();
20 vis[now.x][now.y]=0;
21 for(int i=1;i<=m;i++){
22 int xx=now.x+c[i],l=abs(c[i]*2),tu=abs(now.y-i);
23 if(xx<1||xx>n) continue;
24 if(dis[xx][i]>dis[now.x][now.y]+l+tu){
25 dis[xx][i]=dis[now.x][now.y]+l+tu;
26 if(!vis[xx][i]){
27 tmp.x=xx;
28 tmp.y=i;
29 q.push(tmp);
30 vis[xx][i]=1;
31 }
32 }
33 }
34 }
35 for(int i=1;i<=m;i++){
36 ans=min(ans,dis[n][i]);
37 }
38 ans=ans==1919810?-1:ans;
39 }
40 int main(){
41 scanf("%d%d",&n,&m);
42 for(int i=1;i<=m;i++){
43 scanf("%d",c+i);
44 if(c[i]==0) st=i;
45 }
46 spfa(st);
47 cout<<ans<<endl;
48 return 0;
49 }
T2:买鱼
Problem:
王伯(不是王婆)退休后开始养鱼。他一早起床就赶去动物园,发现这个世界的鱼真不少,五光十色、色彩斑斓,大的、小的,什么都有。这些鱼实在是太美了,买的人越来越多,湖里的鱼越来越少。没有美丽的鱼哪里有美丽的湖?于是动
物园不得不规定,对于每种鱼,每个人最多可以买一条。并且有些鱼不能一起买的,因为它们之间会相互争斗吞食。
王伯想买尽可能多的鱼,但很可惜,他的资金有限。他冥想苦思,不知道如何是好。请编写一个程序帮助他。如果有多个方案都能买尽可能多的鱼,选择所花资金最多的一个。
Code:
1 #include<bits/stdc++.h>
2 using namespace std;
3 int ans,m,n,co[50];
4 long long ansb,ansco;
5 long long st[50];
6 void dfs(int now,int tot,int mon,long long can,long long sta){
7 if(now==n+1){
8 if(tot>ans){
9 ans=tot;
10 ansco=mon;
11 ansb=sta;
12 }
13 else{
14 if(tot==ans){
15 if(mon>ansco){
16 ans=tot;
17 ansco=mon;
18 ansb=sta;
19 }
20 }
21 }
22 return;
23 }
24 if((can&(1<<now))&&mon+co[now]<=m){
25 long long to=can&(~(1<<now));
26 to=to&st[now];
27 dfs(now+1,tot+1,mon+co[now],to,sta|(1<<now));
28 }
29 dfs(now+1,tot,mon,can,sta);
30 }
31 int main(){
32 scanf("%d%d",&m,&n);
33 for(int i=1;i<=n;i++){
34 int x,y;
35 scanf("%d%d",&x,&y);
36 co[x]=y;
37 }
38 for(int i=0;i<=n;i++){
39 st[i]=(1ll<<(n+1))-1;
40 }
41 int x,y;
42 while(1){
43 scanf("%d%d",&x,&y);
44 if(x==0&&y==0) break;
45 if(x==0||y==0) continue;
46 st[x]&=~(1<<y);
47 st[y]&=~(1<<x);
48 }
49 dfs(1,0,0,st[0],0);
50 cout<<ans<<" "<<ansco<<endl;
51 for(int i=1;i<=n;i++){
52 if(ansb&(1<<i)){
53 cout<<i<<endl;
54 }
55 }
56 return 0;
57 }
T3:登山
Problem:
Freda 和 rainbow 只好花钱让它们坐索道下山。索道上的缆车最大承重量为W，而 N 只小猫的重量分别是 C1、C2……CN。当然，每辆缆车上的小猫的重量之和不能超过 W。每租用一辆缆车，Freda 和 rainbow 就要付 1 美元，所以他们想知道，最少需要付多少美元才能把这 N 只小猫都运送下山？
Code:
1 #include<bits/stdc++.h>
2 using namespace std;
3 int n,w;
4 struct state{
5 int c,s;
6 }all[530000];
7 queue<int>q;
8 int wight[20];
9 int vis[530000],init[530000];
10 int main(){
11 scanf("%d%d",&n,&w);
12 for(int i=1;i<=n;++i) scanf("%d",&wight[i]);
13 int nd=(1<<(n+1))-1;
14 q.push(nd);
15 vis[nd]=1;
16 init[nd]=1;
17 all[nd].c=1,all[nd].s=w;
18 while(!q.empty()){
19 int now=q.front();
20 init[now]=0;
21 q.pop();
22 for(int i=1;i<=n;++i){
23 if(now&1<<i){
24 int to=now^(1<<i);
25 int totot=all[now].c,tore=all[now].s;
26 if(tore<wight[i]){
27 totot++;
28 tore=w-wight[i];
29 }
30 else tore-=wight[i];
31 if(vis[to]){
32 if(totot>all[to].c) continue;
33 if(totot==all[to].c){
34 if(tore<all[to].s) continue;
35 }
36 }
37 else vis[to]=1;
38 all[to].c=totot;
39 all[to].s=tore;
40 if(!init[to]){
41 q.push(to);
42 init[to]=1;
43 }
44 }
45 }
46 }
47 printf("%d",all[1].c);
48 return 0;
49 }