FAFU 1136 最长递增子序列

http://acm.fafu.edu.cn/problem.php?id=1136 根据dp建边，建边的时候记得判断如果原本数的大小就ok了 好久没在自家OJ上刷了

#include <iostream>

#include<string.h>

#include<cstdio>

#include<queue>

#include<vector>

//称这个机会吧EK 和DINIC都写一遍复习一下;

using namespace std;

int dp[1105],a[1105],n,max_val,NUM;

int map[1105][1105],flow[1105][1105];

int first[1105],next[1000000],v[1000000];

int dist[1105];

void add(int a,int b)

{

    v[NUM]=b;next[NUM]=first[a];first[a]=NUM;NUM++;v[NUM]=a;next[NUM]=first[b];first[b]=NUM;NUM++;

}

void dpw()

{

    max_val=0;

    int i,j;

    for(i=1;i<=n;i++)

    {

        dp[i]=1;

        for(j=1;j<i;j++)

             if(a[j]<=a[i]&&dp[i]<dp[j]+1)

                  dp[i]=dp[j]+1;

		if(dp[i]>max_val)

        max_val=dp[i];

    }

}

void build()

{

    int i,j;

    for(i=1;i<=n;i++)

    {

        add(i,i+n+1);

		map[i][i+n+1]=1;

        if(dp[i]==1)

        {

               map[0][i]=1;

               add(0,i);

		}

        if(dp[i]==max_val)

        {

            map[i+n+1][n+1]=1;

            add(i+n+1,n+1);

        }else

		{

           for(j=i+1;j<=n;j++)

              if(dp[j]==dp[i]+1&&a[i]<=a[j])

			  {

                add(i+1+n,j);

				map[i+n+1][j]=1;

			  }

		}

    }

}

bool BFS()

{

    memset(dist,-1,sizeof(dist));

    queue<int>q;

    q.push(0);

    int i,x,vv;

    dist[0]=0;

    while(!q.empty())

    {

        x=q.front();

        q.pop();

        for(i=first[x];i!=-1;i=next[i])

        {

            vv=v[i];

            if(dist[vv]==-1&&map[x][vv]>flow[x][vv])

            {

             dist[vv]=dist[x]+1;

             q.push(vv);

            }

        }

    }

    if(dist[n+1]==-1)return false;

     return true;

}

int min_val(int a,int b){return a>b?b:a;}

int find(int x,int low)

{

    int i,a=0,vv;

    if(x==n+1)return low;

    for(i=first[x];i!=-1;i=next[i])

    {

       vv=v[i];

        if(map[x][vv]>flow[x][vv]&&(dist[x]+1==dist[vv])&&(a=find(vv,min_val(low,map[x][vv]-flow[x][vv]))))

       {

         flow[x][vv]+=a;

         flow[vv][x]-=a;

         return a;

        }

    }

    return 0;

}

int main()

{

    int i,temp,ans1,ans2;

	while(scanf("%d",&n)==1){

		 for(i=1;i<=n;i++)

        scanf("%d",&a[i]);

		 if(n==1){

        printf("1\n1\n1\n");

		   }else {

		   NUM=0;

        memset(first,-1,sizeof(first));

        memset(map,0,sizeof(map));

        memset(flow,0,sizeof(flow));

        dpw();

        build();

        ans1=ans2=0;

        while(BFS())

        {

            while((temp=find(0,1<<30)))ans1=ans1+temp;

        }

        map[0][1]=10000000;

        map[1][n+1+1]=10000000;

        map[n][n+1+n]=10000000;

        if(map[n+1+n][n+1]) map[n+1+n][n+1]=10000000;

       memset(flow,0,sizeof(flow));

      while(BFS())

        {

            while((temp=find(0,1<<30)))ans2=ans2+temp;

        }

	   printf("%d\n%d\n%d\n",max_val,ans1,ans2);

		   }

	}

    return 0;

}