红色OI再临 @ 2019-07-20 16:43:19
WA了第三个点
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
#define re register int
#define MN 1001
#define inf 1<<30
using namespace std;
int f[MN];
int a[MN];
struct tu{
int v,w,nxt;
}e[MN*2];
int cnt=1,head[MN];
int n,m,s,t,maxflow;
void add(int u,int v,int w){
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].nxt=head[u];
head[u]=cnt;
}
struct front{
int u,edge;
}pre[2*MN];
int vis[MN],dep[MN];
bool bfs(){
memset(dep,0x3f3f3f3f,sizeof(dep));
memset(vis,0,sizeof(vis));
dep[s]=0;
queue<int>q;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=0;
for(re i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(dep[v]>dep[u]+1&&e[i].w){
dep[v]=dep[u]+1;
if(vis[v]==0){
q.push(v);
vis[v]=1;
}
}
}
}
return dep[t]!=0x3f3f3f3f;
}
int dfs(int u,int flow){//flow为当前路上最短边权
int rlow=0;
if(u==t)return flow;
for(re i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(e[i].w&&dep[v]==dep[u]+1){
if(rlow=dfs(v,min(flow,e[i].w))){
e[i].w-=rlow;
e[i^1].w+=rlow;
return rlow;
}
}
}
return 0;
}
int dinic(){
int lowflow;
while(bfs()){
while(lowflow=dfs(s,inf))maxflow+=lowflow;
}
return maxflow;
}
int main(){
scanf("%d",&n);
for(re i=1;i<=n;i++)
scanf("%d",&a[i]),f[i]=1;
s=0;t=2*n+1;
for(re i=2;i<=n;i++)
for(re j=1;j<i;j++)
{
if(a[j]<=a[i])f[i]=max(f[i],f[j]+1);
}
int ans1=0;
for(re i=1;i<=n;i++)
ans1=max(ans1,f[i]);
printf("%d\n",ans1);
if(ans1==1){
printf("%d\n",n);
printf("%d\n",n);
return 0;
}
for(re i=1;i<=n;i++)
add(i,i+n,1),add(i+n,i,0);
for(re i=1;i<=n;i++)
{
if(f[i]==1)add(s,i,1),add(i,s,0);
if(f[i]==ans1)add(i+n,t,1),add(t,i+n,0);
}
for(re i=1;i<=n;i++)
for(re j=1;j<i;j++)
if(a[j]<=a[i]&&f[i]==f[j]+1)add(j+n,i,1),add(i,j+n,0);
printf("%d\n",dinic());
add(1,n+1,inf);add(n+1,1,0);
add(s,1,inf);add(1,s,0);
if(f[n]==ans1)add(n,n*2,inf),add(n*2,n,0),add(n*2,t,inf),add(t,n*2,0);
printf("%d\n",dinic());
return 0;
}
by 红色OI再临 @ 2019-07-20 16:58:30
@foxdemon 确实认识QAQ
by foxdemon @ 2019-07-20 16:59:06
@红色OI再临 居然猜对了qwq
by 红色OI再临 @ 2019-07-20 17:01:05
@foxdemon 他建议我面向数据编程(雾)
by Lovable_Wind @ 2019-07-20 17:03:25
走自己的路
by Lovable_Wind @ 2019-07-20 17:03:37
别听别人的批判
by 红色OI再临 @ 2019-07-20 17:05:24
@klssxbc0002 嗯嗯
批判还是要听的
by 红色OI再临 @ 2019-07-20 17:05:56
错误已找到:数组开小
by Lovable_Wind @ 2019-07-20 17:10:27
@红色OI再临 别听太多在你正常学习并没做错时的批判
by tanao @ 2019-07-29 20:54:55
fAKe!肥克!