数据下载有误

P2766 最长不下降子序列问题

InsomniaFly @ 2022-12-02 11:46:15

帮朋友发的,#11 和 #13 挂了

然而下载数据调的时候 #11 成了锟斤拷

怎么会是呢


#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=880;
const int M=640000;
const int INF=1e11;
int a[880];
int f[880];
int S,T;
int head[N],idx;
void clear(){
    memset(head,-1,sizeof(head));
    idx=0;
}
struct Node{
    int ne;
    int ve;
    int f;
}edge[2*M];
void added(int x,int y,int f){
    edge[idx].ne=head[x];
    edge[idx].ve=y;
    edge[idx].f=f;
    head[x]=idx;
    idx++;
    edge[idx].ne=head[y];
    edge[idx].ve=x;
    edge[idx].f=0;
    head[y]=idx;
    idx++;
}
int d[N];
int q[N];
int cur[N];
bool bfs(){
    int hh=0;
    int tt=0;
    memset(d,-1,sizeof(d));
    q[0]=S;
    d[S]=1;
    cur[S]=head[S];
    while(hh<=tt){
        int t=q[hh++];
        for(int i=head[t];i!=-1;i=edge[i].ne){
            int ver=edge[i].ve;
            if(d[ver]==-1&&edge[i].f){
                d[ver]=d[t]+1;
                cur[ver]=head[ver];
                if(ver==T){
                    return true;    
                }
                q[++tt]=ver;
            }
        }
    }
    return false;
}
int find(int u,int limit){
    if(u==T){
        return limit;
    }
    else{
        int flow=0;
        for(int i=cur[u];i!=-1&&flow<limit;i=edge[i].ne){
            int ver=edge[i].ve;
            if(d[ver]==d[u]+1&&edge[i].f){
                int t=find(ver,min(limit-flow,edge[i].f));
                if(!t) d[ver]=-1;
                else{
                    edge[i].f-=t;
                    edge[i^1].f+=t;
                    flow+=t;
                }
            }
        }
        return flow;
    }
}
int dinic(){
    int r=0;
    int flow;
    while(bfs()){
        while(flow=find(S,INF)){
            r+=flow;
        }
    }
    return r;
}
signed main(){
    int n;
    clear();
    cin>>n;
    S=0;
    T=2*n+10;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        added(i,i+n,1);
        f[i]=1;
    }
    int s=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++){
            if(a[i]>=a[j]){
                f[i]=max(f[i],f[j]+1);
                s=max(s,f[i]);
            }
        }
        for(int j=1;j<i;j++){
            if(f[i]==f[j]+1&&a[i]>=a[j]) added(j+n,i,1);
        }
        if(f[i]==1) added(S,i,1);
    }
    for(int i=1;i<=n;i++){
        if(f[i]==s) added(i+n,T,1);
    }
    if(s==1){
        cout<<s<<endl<<n<<endl<<n<<endl;
        return 0;
    } 
    else{
        cout<<s<<endl;
        int res=dinic();
        cout<<res<<endl;
        added(S,1,INF);
        added(1,1+n,INF);
        added(n,2*n,INF);
        if(f[n]==s){
            added(2*n,T,INF);
        }
        cout<<res+dinic();
    }
    return 0;
} 

by 离散小波变换° @ 2022-12-02 11:52:01

@InsomniaFly 可能是编辑器的问题。一些比较弱智的编辑器会把好端端的数字识别成奇怪的编码,不知道咋回事。

可以试试写字板,或者用别的什么编辑器。


by 离散小波变换° @ 2022-12-02 11:53:11

拿 VSC 看了一下,数据应该是没问题的


by InsomniaFly @ 2022-12-02 11:53:35

@离散小波变换° 哦哦好的()


by InsomniaFly @ 2022-12-02 11:53:59

感谢()


by _cyh0412_ @ 2022-12-02 13:36:45

问一下楼主

你的记事本默认使用的是UTF-8还是ANSI


by _cyh0412_ @ 2022-12-02 13:36:56

@InsomniaFly


by InsomniaFly @ 2022-12-02 15:09:25

@cyh0412 已经解决了 谢谢你)


by _cyh0412_ @ 2022-12-03 12:10:07

@InsomniaFly 如果下次还遇到这种问题,就看看记事本使用的是UTF-8还是ANSI,改成对应的就好了


|