[题解] P3052

竟然没有看到 dijkstra 的题解，写一发

主要思路

一看

N

很小，考虑状压。

我们用

f

表示某种选择牛的情形，第

i

位上为

1

表示第

i

只牛已经坐电梯下楼了/已经在电梯上了，为

0

表示还没有。

我们对于每个不同的

f

看作不同的节点，则对于每个节点，我们记录：

$w_i$ 表示最近一部电梯（还没下楼）里面的牛已经占了多少空间
$dis_i$ 表示达到当前情形已经送走了几部电梯（还没下楼的不算）

对于某个节点，如果我们当前情形是能通过把一只牛送上电梯这个操作来达到它对应的情形，那么就对它建边。即我们对所有一步可达的节点建边。

对于 dijkstra 的三角形不等式，我们也进行改造。令

w1

为

w_u + c_i

d1

为

dis_u

。如果

w1 > W

, 则将

w1

修改为

c_i

，将

d1

增加一。即用

w1

，

d1

表示把第

i

只牛送上电梯后对应节点的

w

和

dis

。

对于如下条件:

$dis_v > d1$
$dis_v = d1$ 并且 $w_v > w1$

如果有任意一个满足，就对节点

v

进行松弛操作。

最后输出所有牛都上电梯的对应情形的

dis_{f_{max}}

+ 1

即可（最后一趟电梯也要算）。

对于部分证明的补充

dijkstra的贪心为什么是对的：我们在队列优化时，依照 $k = dis_i * W + w_i$ $k = d i s_{i} * W + w_{i}$ 排序（由于 $W$ $W$ 一定大于等于 $w_i$ $w_{i}$ ，即以 $dis$ $d i s$ 为第一关键字， $w$ $w$ 为第二关键字排序）。
- 我们注意到， $k \ge \sum{c_i}$
- 我们发现，对于某个解 $k_i$ ，如果存在另一个解 $k_j$ ，使得 $k_i \ge k_j$ ，答案至少不会更劣（相等或 $dis$ 更小或 $w$ 更小）。
- 显然没有负环

故dijkstra做法能够保障正确性，复杂度大致在

2^n n^2

。

AC代码

CPP

#include <bits/stdc++.h>

#define N 300050
#define int long long
#define maxf ((1 << n) - 1)
#define inf 0x3f3f3f3f3f3f3f3f

using namespace std;

struct node{
	int v, w;
	bool operator < (const node &a) const {return w > a.w;}
};

int n, W;
int c[N], dis[N], w[N];
bool vis[N];

signed main(){
	cin >> n >> W;

	for(int i = 0ll; i < n; i++) cin >> c[i];

	memset(dis, 0x3f, sizeof dis); dis[0] = 0ll; w[0] = 0ll;
	priority_queue <node> q; q.push({0ll, 0ll});

	while(!q.empty()){
		int u = q.top().v; q.pop();
		if(vis[u]) continue; vis[u] = true;
		for(int i = 0; i < n; i++){
			if(u & (1ll << i)) continue;
			int v = u | (1ll << i);
			int d1 = dis[u], w1 = w[u] + c[i];
			if(w1 > W) d1++, w1 = c[i];
			if(dis[v] > d1 || (dis[v] == d1 && w[v] > w1)){
				dis[v] = d1; w[v] = w1;
				q.push({v, dis[v] * W + w[v]});
			}
		}
	}

	cout << dis[maxf] + bool(w[maxf]);

	return 0;
}

文章操作

主要思路

对于部分证明的补充

AC代码

相关推荐

评论

[题解] P3052