elpsconr @ 2024-08-02 01:45:11
不知道为啥用now用for循环赋值就会超时,直接memcpy就可以通过,memcpy会优于for循环吗??不会像memset一样被卡吗
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
#define cy cout<<"YES"<<endl
#define cn cout<<"NO"<<endl
const int N=3e3+6,yyx=4e9+7;
int n,m,s,t,a[N],st[N],dp[N];
int h[N],idx,d[N],now[N];
struct edge{
int to,ne,w;
}e[N<<1];
void add(int u,int v,int w){
e[idx].to=v;e[idx].w=w;e[idx].ne=h[u];h[u]=idx++;
}
void _add(int u,int v,int w){
add(u,v,w);
add(v,u,0);
}
int bfs(){
queue<int> q;
memset(d,0,sizeof d);
q.push(s);d[s]=1;
while(q.size()){
int u=q.front();q.pop();
for(int i=h[u];~i;i=e[i].ne){
int j=e[i].to;
if(e[i].w>0&&!d[j]){
int j=e[i].to;
d[j]=d[u]+1;
q.push(j);
}
}
}
return d[t];
}
int dfs(int u,int dis){
if(u==t) return dis;
for(int& i=now[u];~i;i=e[i].ne){//&符号,在i++的同时,now[u]也跟着改变
int j=e[i].to;
if(d[j]==d[u]+1&&e[i].w){
int di=dfs(j,min(dis,e[i].w));
if(di){
e[i].w-=di;e[i^1].w+=di;
return di;
}
}
}
return 0;
}
int dinic(){
int ans=0;
while(bfs()){
memcpy(now,h,sizeof h);//用for就不行,不知道为啥
//for(int i=1;i<=2*n+1;++i) now[i]=h[i];
while(int di=dfs(s,yyx)) ans+=di;
}
return ans;
}
void solve(){
cin>>n;
memset(h,-1,sizeof h);
s=0,t=2*n+1;
for(int i=1;i<=n;++i) cin>>a[i],dp[i]=1;
for(int i=1;i<=n;++i){
for(int j=1;j<i;++j){
if(a[i]>=a[j]) dp[i]=max(dp[i],dp[j]+1);
}
}
int l=0;
for(int i=1;i<=n;++i) l=max(l,dp[i]);
if(l==1){
cout<<l<<"\n"<<n<<"\n"<<n<<endl;return;
}
cout<<l<<endl;
for(int i=1;i<=n;++i) _add(i,i+n,1);
for(int i=1;i<=n;++i) if(dp[i]==1) _add(s,i,1);
for(int i=1;i<=n;++i) if(dp[i]==l) _add(i+n,t,1);
for(int i=1;i<=n;++i){
for(int j=1;j<i;++j){
if(a[i]>=a[j]&&dp[i]==dp[j]+1) _add(j+n,i,1);
}
}
int ans=dinic();
cout<<ans<<endl;
_add(1,1+n,yyx);_add(s,1,yyx);
if(dp[n]==l) _add(n,n*2,yyx),_add(n*2,t,yyx);
ans+=dinic();
cout<<ans<<endl;
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
int _=1;
//cin>>_;
while(_--)
solve();
return 0;
}//dinic算法
by FerventTemp0 @ 2024-08-02 01:46:50
memset 为啥会被卡,你自己的问题吧
by elpsconr @ 2024-08-02 01:49:09
我的问题i应该从0开始,但是还有一个问题,memcpy会不会被卡,和for循环相比哪个更优
by elpsconr @ 2024-08-02 01:55:14
@FerventTemp0 请审题
by qczrz6v4nhp6u @ 2024-08-02 07:27:14
@elpsconr
memset 会被卡是因为多测,你又访问了整个数组,这样的复杂度就是 memset(arr,val,len*(sizeof type))
的形式即可,其中 arr
的类型是 type*
,len
为需要操作的长度。
memcpy 同理。
by EXODUS @ 2024-08-02 07:30:38
memcpy 是优的,原因好像是它底层操作时是对一个 bite 操作,这样好像可以带一个
by qczrz6v4nhp6u @ 2024-08-02 07:32:29
memset 与 memcpy 在常数上均优于朴素的 for 循环,但仅仅是常数差别。你的代码 T 了只是因为你的 for 循环没有给 0 赋值,这样 Dinic 的复杂度就有问题。
by Kev1nL1kesCod1ng @ 2024-08-02 07:53:43
hina /se/se
by Alan_Zhao @ 2024-08-20 19:17:54
@EXODUS 对一个咬操作