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 ♂蒟·蒻 @ 2018-11-24 10:08:22
看不懂
by 我没有开挂 @ 2018-11-24 10:23:12
%%%%%%%%%巨佬orz
by EndSaH @ 2018-11-24 10:26:00
by SkyLiYu @ 2018-11-24 10:44:12
@HNYLMS_MuQiuFeng 麻烦您把用不到的库和define删掉可以么（如果都用了那我只能%%%
by HNYLMS_MuQiuFeng @ 2018-11-24 10:59:52
@隔壁小邱 哦好的
by HNYLMS_MuQiuFeng @ 2018-11-24 11:00:27
@隔壁小邱 请稍等大约15min
by HNYLMS_MuQiuFeng @ 2018-11-24 11:30:10
//Code by muq
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int inf = 2147483647;
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;
memset(dep, 0, sizeof(dep));
dep[s] = 1;
q.push(s);
do {
int u = q.front();
q.pop();
for(int i = head[u]; i; i = a[i].next) {
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()) {
for(int i = s; i <= t; ++i) {
cur[i] = head[i];
}
while(int d = dfs(s, inf)) {
ans += d;
}
}
return ans;
}
int main(void) {
ios::sync_with_stdio(0);
cin >> n;
s = 0, t = 2 * n + 1;//开始没写真尴尬……还好想起来了不然要凉2333
for(int i = 1; i <= n; ++i) {
cin >> nu[i];
dp[i] = 1;
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j < i; ++j) {
if(nu[j] <= nu[i])
dp[i] = max(dp[i], dp[j] + 1);
}
}
for(int i = 1; i <= n; ++i)
ma = max(ma, dp[i]);
for(int i = 1; i <= n; ++i) {
if(dp[i] == 1)
addedge(s, i, 1);
if(dp[i] == ma)
addedge(i + n, t, 1);
}
for(int i = 1; i <= n; ++i) {
addedge(i, i + n, 1);
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j < i; ++j) {
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;
}@隔壁小邱
抱歉刚刚电脑出了点问题
by SkyLiYu @ 2018-11-24 11:58:38
@HNYLMS_MuQiuFeng dinic咕咕？
by SkyLiYu @ 2018-11-24 12:00:14
@HNYLMS_MuQiuFeng 你有没有拿数据拍一拍你是哪里错了？
by HNYLMS_MuQiuFeng @ 2018-11-24 12:35:49
@隔壁小邱 拿不到数据，只知道 WA的两个点都是第二问