传送门：https://www.luogu.org/problemnew/show/P2766
从WC2017讲义上看到的这题，然后发现luogu上有。。。
对于第一问，先是直接一个二维的DP（虽然可以优化），然后将一个数拆成两个点，中间连一条容量为1的边。对于\(dp[i]=1\)的点，从源点向它连边，对于\(dp[i]=ans\)的点，从它向汇点连边，然后跑Dinic即可。最后一问应该取消相关的容量限制，但是搞了我好久。。。我好弱啊QAQ
AC代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 |
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <queue> using namespace std; const int MAXN = 1010; const int INF = 20000000; struct Edge { int from,to,cap,flow; Edge() {} Edge(int from,int to,int cap,int flow): from(from),to(to),cap(cap),flow(flow) {} }; struct Dinic{ int n,m,s,t; vector <Edge> edges; vector <int> g[MAXN]; bool visit[MAXN]; int dist[MAXN]; int cur[MAXN]; void addedge(int from,int to,int cap) { edges.push_back(Edge(from,to,cap,0)); edges.push_back(Edge(to,from,0,0)); m = edges.size(); g[from].push_back(m-2); g[to].push_back(m-1); } bool bfs() { memset(visit,0,sizeof visit); queue<int> q; q.push(s); dist[s] = 0; visit[s] = 1; while(!q.empty()) { int now = q.front(); q.pop(); for(int i = 0; i < g[now].size(); ++i) { Edge &e = edges[g[now][i]]; if(!visit[e.to] && e.cap > e.flow) { visit[e.to] = 1; dist[e.to] = dist[now] + 1; q.push(e.to); } } } return visit[t]; } int dfs(int x,int res) { if(x == t || !res) return res; int flow = 0,f; for(int i = 0; i < g[x].size(); ++i) { Edge &e = edges[g[x][i]]; if(dist[x] + 1 == dist[e.to] && (f = dfs(e.to,min(res,e.cap - e.flow))) > 0) { e.flow += f; edges[g[x][i]^1].flow -= f; flow += f; res -= f; if(!res) break; } } return flow; } }dinic; int n; int xu[MAXN],dp[MAXN]; int get_1(int i) { return 2*i-1; } int get_2(int i) { return 2*i; } int main() { scanf("%d",&n); for(int i = 1; i <= n; ++i) scanf("%d",xu+i); dp[1] = 1; for(int i = 2; i <= n; ++i) { dp[i] = 1; for(int j = 1; j < i; ++j) if(xu[j] <= xu[i]) dp[i] = max(dp[i],dp[j]+1); } int ans = -1; for(int i = 1; i <= n; ++i) ans = max(ans,dp[i]); printf("%d\n",ans); for(int i = 1; i <= n; ++i) dinic.addedge(get_1(i),get_2(i),1); for(int i = 1; i <= n; ++i) { if(dp[i] == 1) { dinic.addedge(0,get_1(i),1); } if(dp[i] == ans) { dinic.addedge(get_2(i),2*n+1,1); } } for(int i = 1; i <= n; ++i) for(int j = i+1; j <= n; ++j) if(xu[i] <= xu[j] && dp[i]+1 == dp[j]) {dinic.addedge(get_2(i),get_1(j),1);} dinic.s = 0; dinic.t = 2*n+1; int ans1 = 0; while(dinic.bfs()) ans1 += dinic.dfs(0,INF); printf("%d\n",ans1); dinic.addedge(get_1(1),get_2(1),INF); dinic.addedge(0,get_1(1),INF); if(dp[n] == ans) dinic.addedge(get_1(n),get_2(n),INF),dinic.addedge(get_2(n),2*n+1,INF); while(dinic.bfs()) ans1 += dinic.dfs(0,2*n+1); printf("%d\n",ans1); return 0; } |