로곡 P2766 최장 불하강 서열 문제 최대 유분층 구성도
2099 단어 도론 알고리즘
로곡 P2766 최장 하강 서열 문제
먼저 dp로 최장 상승 서열 해결 문제 구하기 (1)
그리고 각 수분해점은 유량이 1인 변을 연결하고 a[i]<=a[j]와 i
문제(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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BZOJ1003] [ZJOI2006] 물류운송(최단로+dp)전송문 예처리costi, j는 i일째부터 j일째까지 이 길의 최단길을 뛴다는 것을 나타낸다.즉 경로상의 모든 점이 i에서 j일까지 뛸 수 있는 전제에서 가장 짧은 길이라는 것이다.그리고fi는 이전 i일의 최소 비용을...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.