关于memcpy

P2766 最长不下降子序列问题

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 会被卡是因为多测,你又访问了整个数组,这样的复杂度就是 O(Tn) 而非 O(\sum n) 的。只需要将 memset 改为 memset(arr,val,len*(sizeof type)) 的形式即可,其中 arr 的类型是 type*len 为需要操作的长度。

memcpy 同理。


by EXODUS @ 2024-08-02 07:30:38

memcpy 是优的,原因好像是它底层操作时是对一个 bite 操作,这样好像可以带一个 \dfrac{1}{8} 的常数。memset 同理。


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 对一个咬操作


|