好哦 是独立(并没有)做出来的第一道 *2700
看到前几天的 edu yzhang 切了 F,于是跑去看了看题
发现是个网络流,于是捡起了快一年没碰的网络流复习(
注意到这个有先决条件的选数 以及数据范围都长得很像最大权闭合子图模型,于是用这个模型去做。
超级源 向每个正权点 ( 为正的数)连流量为 的边,每个负权点 ( 为负的数)向超级汇 连流量为 的边,所有满足 且 的有序对 连边 ,权值为 。答案即为所有正权点之和减去最小割。
到这里还没有结束,我们注意到有一个毒瘤的 32MB 的空间限制,而直接连边的话边数是 级别的,刚好被卡掉。
考虑优化一下连边:如果已经有边 , 存在,我们就不需要再连 的边。开一个 数组表示 是否还需要连边(刚好能开下)即可,连边数量降到了线性。
// 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;
}