【题解】CF1473F

好哦 是独立（并没有）做出来的第一道 *2700

看到前几天的 edu yzhang 切了 F，于是跑去看了看题

发现是个网络流，于是捡起了快一年没碰的网络流复习（

注意到这个有先决条件的选数 以及数据范围都长得很像最大权闭合子图模型，于是用这个模型去做。

超级源 $S$ 向每个正权点 $i$（$b_i$ 为正的数）连流量为 $b_i$ 的边，每个负权点 $i$（$b_i$ 为负的数）向超级汇 $T$ 连流量为 $-b_i$ 的边，所有满足 $a_j\ |\ a_i$ 且 $i\in [1,n],\ j\in [1,i-1]$ 的有序对 $(i,j)$ 连边 $(i,j)$，权值为 $\texttt{INF}$。答案即为所有正权点之和减去最小割。

到这里还没有结束，我们注意到有一个毒瘤的 32MB 的空间限制，而直接连边的话边数是 $10^7$ 级别的，刚好被卡掉。

考虑优化一下连边：如果已经有边 $(i,j)$，$(j,k)$ 存在，我们就不需要再连 $(i,j)$ 的边。开一个 $\texttt{vis}$ 数组表示 $(i,j)$ 是否还需要连边（刚好能开下）即可，连边数量降到了线性。

// 2021.01.17
// Code by LTb
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch;
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    return f*x;
}
inline void chmax(int &x,int y){x=max(x,y);}
inline void chmin(int &x,int y){x=min(x,y);}

const int INF=1e9+7;
const int MAXN=3005;
const int MAXM=20005;
int s,t;
int Index=0;
int w[MAXM*2];
vector<int> v[MAXN];
int point[MAXM*2];
int label[MAXN];
int cur[MAXN*2];

void add_edge(int x,int y,int f){
	v[x].push_back((++Index)*2);
	v[y].push_back(Index*2+1);
	w[Index*2]=f;
	w[Index*2+1]=0;
	point[Index*2]=y;
	point[Index*2+1]=x;
}

bool bfs(){
	memset(label,0,sizeof(label));
	memset(cur,0,sizeof(cur));
	queue<int> q;
	q.push(s);
	label[s]=1;
	while (!q.empty()){
		int now=q.front();
		q.pop();
		for (int i=0;i<v[now].size();i++){
			int edge=v[now][i];
			int u=point[edge];
			if (!label[u] && w[edge]){
				label[u]=label[now]+1;
				q.push(u);
			}
		}
	}

	return label[t]!=0;
}

int dfs(int p,int limit){
	if (limit==0||p==t) return limit;

	int used=0;
	for (int i=cur[p];i<v[p].size();i++){
		cur[p]=i;
		int edge=v[p][i];
		int u=point[edge];
		if (w[edge] && label[p]+1==label[u]){
			int flow=dfs(u,min(limit-used,w[edge]));
			used+=flow;
			w[edge]-=flow;
			w[edge^1]+=flow;
			if (used==limit) break;
		}
	}

	return used;
}

int dinic(){
	int ans=0;
	while (bfs())
		ans+=dfs(s,INF);
	return ans;
}

int n;
int a[MAXN],b[MAXN];
int sum=0;
bool vis[MAXN][MAXN];

signed main()

{
	n=read();
	s=0;t=n+1;
	for (int i=1;i<=n;i++)
		a[i]=read();

	for (int i=1;i<=n;i++){
		b[i]=read();
		if (b[i]>0) {sum+=b[i];add_edge(s,i,b[i]);}
		else add_edge(i,t,-b[i]);

		for (int j=i-1;j>=1;j--){
			if (a[i]%a[j]==0 && !vis[i][j]){
				add_edge(i,j,INF);
				vis[i][j]=true;
				for (int k=1;k<j;k++)
					vis[i][k]|=vis[j][k];
			}
		}
	}

	cout<<sum-dinic()<<endl;
	return 0;
}