題目

啥都不會只能來寫寫題解了

第一問先搞一個\(dp\)吧，小學生水平的\(dp\)

第二問要求每一個點只能使用一次，顯然要先拆點，把\(i\)拆成\(i\)與\(i'\)，之后\(i\)于\(i'\)連容量為\(1\)的邊

之后能產(chǎn)生長度為\(ans\)的LIS需要滿足什么條件呢，顯然得從一個\(dp[i]=1\)的點開始，從一個\(dp[i]=ans\)的點結(jié)束，否則就不可能產(chǎn)生長度為\(ans\)的LIS了

同時我們還得考慮到我們這是一個\(dp\)，所以只能是讓\(i\)的所有轉(zhuǎn)移點向\(i\)連邊

第三問取消\(1\)和\(n\)的限制就好了

代碼

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<queue> #define maxn 1105 #define re register #define LL long long #define inf 99999999 #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) inline int read() {char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x; } struct E{int v,nxt,w,f;}e[2000005]; int dp[maxn],a[maxn],ans,n,num=1,S,T,tot,cnt; int d[maxn],head[maxn],cur[maxn]; inline void add(int x,int y,int z) {e[++num].v=y;e[num].w=z;e[num].nxt=head[x];head[x]=num;} inline void C(int x,int y,int z) {add(x,y,z),add(y,x,0);} inline int BFS() {std::queue<int> q;for(re int i=S;i<=T;i++) d[i]=0,cur[i]=head[i];d[S]=1,q.push(S);while(!q.empty()){int k=q.front();q.pop();for(re int i=head[k];i;i=e[i].nxt)if(!d[e[i].v]&&e[i].w>e[i].f) d[e[i].v]=d[k]+1,q.push(e[i].v);}return d[T]; } int dfs(int x,int now) {if(x==T||!now) return now;int flow=0,ff;for(re int& i=cur[x];i;i=e[i].nxt)if(d[x]+1==d[e[i].v]){ff=dfs(e[i].v,min(e[i].w-e[i].f,now));if(ff<=0) continue;now-=ff,flow+=ff;e[i].f+=ff,e[i^1].f-=ff;if(!now) break;}return flow; } int main() {n=read();if(n==1) {puts("1");puts("1"),puts("1");return 0;}for(re int i=1;i<=n;i++) a[i]=read(),dp[i]=1;for(re int i=1;i<=n;i++)for(re int j=1;j<i;j++)if(a[j]<=a[i]) dp[i]=max(dp[i],dp[j]+1);for(re int i=1;i<=n;i++) ans=max(ans,dp[i]);S=0,T=n+n+1; for(re int i=1;i<=n;i++) C(i,i+n,1);for(re int i=1;i<=n;i++)if(dp[i]==1) C(S,i,1);for(re int i=1;i<=n;i++)if(dp[i]==ans) C(i+n,T,1);for(re int i=1;i<=n;i++)for(re int j=1;j<i;j++)if(a[j]<=a[i]&&dp[i]==dp[j]+1) C(j+n,i,1);while(BFS()) tot+=dfs(S,inf);num=1;memset(e,0,sizeof(e)),memset(head,0,sizeof(head));for(re int i=2;i<n;i++) C(i,i+n,1);for(re int i=2;i<n;i++)if(dp[i]==1) C(S,i,1);for(re int i=2;i<n;i++)if(dp[i]==ans) C(i+n,T,1);C(1,1+n,inf),C(n,n+n,inf);if(dp[1]==1) C(S,1,inf);if(dp[1]==ans) C(1+n,T,1);if(dp[n]==1) C(S,n,1);if(dp[n]==ans) C(n+n,T,inf);for(re int i=1;i<=n;i++)for(re int j=1;j<i;j++)if(a[j]<=a[i]&&dp[i]==dp[j]+1) C(j+n,i,1);while(BFS()) cnt+=dfs(S,inf);printf("%d\n%d\n%d\n",ans,tot,cnt);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/asuldb/p/10293207.html

總結(jié)

以上是生活随笔為你收集整理的【[网络流二十四题]最长不下降子序列问题】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。