#C241022B. 工厂

标签（Label）

状态压缩
动态规划
模拟退火

网址（Website）

题目详情 - 工厂 - Super

题解 - 工厂 - Super

题解（Solution）

模拟退火

$\qquad$发现不知道应该以什么顺序加入工厂，考虑模拟退火，每次修改两个工厂的位置，计算答案。

$\qquad$因为每一次计算只需要花费 $O(nlog_n)$ 的时间，复杂度非常小，直接大胆跑。

$\qquad$预计得分：$\text{100pts}$ 。

出题者题解

算法分析

考虑每座工厂是用谁生产的原材料做的，将形成一棵有根树。如果这棵有根树确定了，我们可以树形 $DP$ 算出答案：记 $f_u$ 为以 $u$ 为根的答案，那么 $f_u = \max_{i=0}^{l-1} a_u(\lfloor \frac{i}{b_u} \rfloor + 1) + f_{v_i}$，其中 $v_0, v_1, \cdots, v_{u-1}$ 为 $u$ 的儿子并且 $f_{v_i}$ 单调减。

注意到树形 $DP$ 中计算一个点的 $f$ 值只需要用到儿子的 $f$ 值，因此对于原题，可以状压 $DP$，记 $dp_S$ 为 $S$ 这个子集的答案，那么 $dp_S = \max_{u \in S, {u} \cup T_0 \cup T_1 \cup \cdots T_{l-1} = S} \max_{i=0}^{l-1} a_u(\lfloor \frac{i}{b_u} \rfloor + 1) + dp_{T_i}$，其中 $l$ 是任意的。

直接枚举 $u$ 和 $i$ 的复杂度为 $O(n^2 \cdot 3^n)$。

记 $h_{u,S} = \max_{T_0 \cup T_1 \cup \cdots T_{l-1} = S} \max_{i=0}^{l-1} a_u \lfloor \frac{i}{b_u} \rfloor + dp_{T_i}$，则
$dp_S = a_u + \min_{u \in S} h_{u,S \backslash {u}}$。
把 $b_u$ 个 $T$ 合在一起考虑。记 $g_{k,S} = \min_{T_0 \cup T_1 \cup \cdots \cup T_{k-1} = S} \max_i dp_{T_i}$，则 $g_{k,S} = \min_{T \subseteq S} \max { g_{k-1, S-T}, dp_T }$， $h_{u,S} = \min_{T \subseteq S} \max { g_{b_u, T}, a_u + h_{u, S \backslash T} }$。

复杂度变为 $O(n3^n)$。

代码（Code）

模拟退火

#include<bits/stdc++.h>
#include<vector>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 32;
bool ST;
mt19937_64 rr(time(0));
inline int rnd(int l,int r){return rr()%(r-l+1)+l;}
inline double rndd(double l, double r){return 1.*rnd(1,100000)/1e5*(r-l)+l;}

int n, ans = inf;
P d[N];

priority_queue<P> q;
int calc(){
	while(q.size()) q.pop();
	q.emplace(-d[1].x,1);
	int c = 2;
	while(q.size()){
		int t,i;tie(t,i)=q.top();q.pop();
		q.emplace(t-d[i].x, i);
		for(int tmp = d[i].y;tmp && c<=n;c++,tmp--)
			q.emplace(t-d[c].x, c);
		if(c==n+1) return ans = min(ans, -t), -t;
	}return 0;
}

void SA(){
	int cur = calc();
	for(double T = 1e9; T>=1e-9; T*=0.9995){
		int l = rnd(1,n), r = rnd(1,n);
		if(l>r) swap(l,r);
		swap(d[l], d[r]);
		int now = calc(), delta = now - cur;
		if(exp(-delta/T) > rndd(0,1)) cur = now;
		else swap(d[l], d[r]);
	}
}

void Solve(){
	n = rd();For(i,1,n) d[i]={rd(),rd()};
	sort(d+1,d+n+1,[&](auto a,auto b){return a.x*b.y < a.y*b.x;});
	while(clock()/CLOCKS_PER_SEC<=3.9) SA();
	printf("%lld\n",ans);
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("factory.in","r",stdin);
	freopen("factory.out","w",stdout); 
	int T = 1, Tim = clock();
	while(T--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}