HNYLMS_MuQiuFeng @ 2018-11-24 10:00:14
//Code by muq
#include<set>
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define fi first
#define se second
#define mp make_pair
#define lll long long
#define inf 2147483647
#define pii pair<int,int>
#define io0 ios::sync_with_stdio(0)
#define ppi pair<pair<int,int>,int>
#define me(a,b) memset(a,b,sizeof(a))
#define reph(i,a,b) for(i=a;i<=b;++i)
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define rap(i,a,b) for(int i=a;i>=b;--i)
#define repp(i,a,b,c) for(int i=a;i<=b;i+=c)
#define lrep(i,a,b) for(long long i=a;i<=b;++i)
#define reg(i,d,head,a) for(int i=head[d];i;i=a[i].next)
using namespace std;
inline void File() {
freopen("muq.in.txt", "r", stdin);
}
int n, s, t, head[500010], nu[600], cur[500010];//一开始把nu(存输入数字的数组)习惯性的定义为a然后存边数组也为a就咕了……
int cnt = 1, dep[500010], dp[600], ma;
int ans1, ans2;
struct edge {
int next, to, wt;
} a[500010];
inline void add(int u, int v, int w) {
a[++cnt] = (edge) {head[u], v, w};
head[u] = cnt;
}
inline void addedge(int u, int v, int w) {
add(u, v, w);
add(v, u, 0);
}
inline int dfs(int u, int flow) {
if(u == t)
return flow;
for(int &i = cur[u]; i; i = a[i].next) {
int to = a[i].to;
if(dep[to] == dep[u] + 1 and a[i].wt) {
int di = dfs(to, min(a[i].wt, flow));
if(di > 0) {
a[i].wt -= di;
a[i^1].wt += di;
return di;
}
}
}
return 0;
}
inline bool bfs() {
queue <int> q;
me(dep, 0);
dep[s] = 1;
q.push(s);
do {
int u = q.front();
q.pop();
reg(i, u, head, a) {
int to = a[i].to;
if(dep[to] == 0 and a[i].wt > 0) {
dep[to] = dep[u] + 1;
q.push(to);
}
}
}while(!q.empty());
return dep[t];
}
inline int Dinic() {
int ans = 0;
while(bfs()) {
rep(i, 0, t) {
cur[i] = head[i];
}
while(int d = dfs(s, inf)) {
ans += d;
}
}
return ans;
}
int main(void) {
//File();
io0;
cin >> n;
s = 0, t = 2 * n + 1;//开始没写真尴尬……还好想起来了不然要凉2333
rep(i, 1, n) {
cin >> nu[i];
dp[i] = 1;
}
rep(i, 1, n) {
rep(j, 1, i - 1) {
if(nu[j] <= nu[i])
dp[i] = max(dp[i], dp[j] + 1);
}
}
rep(i, 1, n)
ma = max(ma, dp[i]);
rep(i, 1, n) {
if(dp[i] == 1)
addedge(s, i, 1);
else if(dp[i] == ma)
addedge(i + n, t, 1);
}
rep(i, 1, n) {
addedge(i, i + n, 1);
}
rep(i, 1, n) {
rep(j, 1, i - 1) {
if(nu[j] <= nu[i] and dp[i] == dp[j] + 1)
addedge(j + n, i, 1);
}
}
ans1 = Dinic();
addedge(s, 1, inf);
addedge(1, n + 1, inf);//写成(n+1,t,inf)……
if(dp[n] == ma) {//如果最后一个数能作为一个最长不下降子序列的终点
addedge(n, n * 2, inf);//一开始写成(s,n,inf)我是不是没救了
addedge(n * 2, t, inf);
}
ans2 = Dinic() + ans1;//这里要加上原来的答案!
cout << ma << endl << ans1 << endl << ans2 << endl;
return 0;
}
哪里错了QAQ
by HNYLMS_MuQiuFeng @ 2018-11-24 12:37:48
@隔壁小邱 Dinic要是有错的话那是哪里呢???求助
by SkyLiYu @ 2018-11-24 18:11:49
@HNYLMS_MuQiuFeng 我没说你dinic有错Q#Q
by SkyLiYu @ 2018-11-24 18:12:50
@HNYLMS_MuQiuFeng 没有数据怎么搞...要不您rand()拍一下吧
by HNYLMS_MuQiuFeng @ 2018-11-24 20:22:09
@隔壁小邱 emmm好叭……明天改
by w4p3r @ 2018-12-02 22:46:57
rep(i, 1, n) {
if(dp[i] == 1)
addedge(s, i, 1);
else if(dp[i] == ma)
addedge(i + n, t, 1);
}
这里的else应该去掉,因为如果这是一个递减的数组(如5 4 3 2 1),ma就会等于1,这时候每个点都应该既对源点建边也对汇点建边,但是这个else会使每个点只和源点建边。
(我才不会告诉你我也是这里错了qwq)
by nosta @ 2018-12-12 22:03:44
@Waper 这么巧,我也错这地儿了。。
by w4p3r @ 2018-12-12 23:30:30
@nosta 23333
by Smokey_Days @ 2019-01-06 20:47:44
@Waper 感谢您提供的全新思路(大雾)
by 斯茂 @ 2019-02-12 20:00:18
特判一个第一问答案为1就好了