로곡 P2766 최장 불하강 서열 문제 최대 유분층 구성도

2099 단어 도론 알고리즘

로곡 P2766 최장 하강 서열 문제


먼저 dp로 최장 상승 서열 해결 문제 구하기 (1)
그리고 각 수분해점은 유량이 1인 변을 연결하고 a[i]<=a[j]와 idp[i]=1, s-----INF-->i의 경우 dp[i]=LIS i+n ------INF--->t,ans=dinic(s,t);문제 해결(2)
문제(3)에 대해 1과 n의 분리된 데이터를 1에서 INF로 바꾸면 된다.ans+=dinic(s,t).문제 해결(3)

특판 LIS=1의 상황.

#include 

using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn = 1500 + 10;
const int maxm = 1000000 + 10;

int n,m,k;
int l[maxn];//    
int h[maxn];//     
int cur[maxn];
int tot = 0;

struct edge
{
  int to;
  int c;
  int next;
  edge(int x = 0, int y = 0, int z = 0) : to(x), c(y), next(z) {}
 }es[maxm*2];//       2 

void add_edge(int u, int v, int c)
{
    es[tot] = edge(v,c,h[u]);
    h[u] = tot++;
    es[tot] = edge(u,0,h[v]);
    h[v] = tot++;
    //cout << u < q;
   q.push(s);
   while(!q.empty())
   {
    int u = q.front();
    //cout  << u <= a[j]) dp[i] = max(dp[i],dp[j]+1);
       maxa = max(maxa,dp[i]);
    }
   tot = 0;
   memset(h,-1,sizeof(h));
   int s = 0, t = 2*n+1;
   add_edge(1,1+n,1);
   add_edge(n,n+n,1);
   for(int i = 1; i <= n; i++)
   {
       if(i != 1 && i != n) add_edge(i,i+n,1);
       if(dp[i] == 1) add_edge(s,i,INF);
       if(dp[i] == maxa) add_edge(i+n,t,INF);
       for(int j = i+1; j <= n; j++)
        if(dp[j] == dp[i]+1 &&a[i] <= a[j]) add_edge(i+n,j,1);
   }
   if(n == 1) {printf("1
1
1
");return 0;} if(maxa == 1) {printf("%d
%d
%d
",1,n,n);return 0;} printf("%d
",maxa); int res = dinic(s,t); printf("%d
",res); es[0].c = INF; es[2].c = INF; res += dinic(s,t); printf("%d
",res); return 0; }

 

좋은 웹페이지 즐겨찾기