最长上升子序列是一个经典问题,可以用O(n^2)的dp解决。给出一个串,求出最长上升子序列的长度为多少?假设长度为s,现在问题是,有多少个长度为s的上升子序列,满足每个子序列所包含的元素均不相同(即一个数只能选一次)。
建模:
第一问直接用dp求解,dp[i]表示以i为结尾的最长递增子序列的长度,最后取dp[1~n]的最大值,即为s。
第二问可以利用上一问求出来的dp数组,用网络流求解。
1. 拆点,将每个点拆成两点,容量为1,保证每个点只取一次。
2. 增加源点s和汇点t,s和dp[i]=1的点相连,dp[i]=s的点和t相连,容量均为INF。
3. 对于两点i和j(j<i),如果满足条件:a[j]<a[i]&&dp[j]+1=dp[i],添加有向边(j,i),容量为INF。
这样,保证从s到t的每一条路都是一条最长递增子序列,最大流即为答案。
例:HDU3998
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 0x7fffffff;
const int maxv = 2000;
const int maxe = maxv*maxv*2;
int n,s;
int a[maxv];
int dp[maxv];
int source,sink;
//
struct Edge
{
int v;
int next;
int flow;
};
Edge e[maxe];
int head[maxv],edgeNum;
int now[maxv],d[maxv],vh[maxv],pre[maxv],preh[maxv];
void addEdge(int a,int b,int c)
{
e[edgeNum].v = b;
e[edgeNum].flow = c;
e[edgeNum].next = head[a];
head[a] = edgeNum++;
e[edgeNum].v = a;
e[edgeNum].flow = 0;
e[edgeNum].next = head[b];
head[b] = edgeNum++;
}
void Init()
{
edgeNum = 0;
memset(head,-1,sizeof(head));
memset(d,0,sizeof(d));
}
int sap(int s,int t,int n) //源点,汇点,结点总数
{
int i,x,y;
int f,ans = 0;
for(i = 0; i < n; i++)
now[i] = head[i];
vh[0] = n;
x = s;
while(d[s] < n)
{
for(i = now[x]; i != -1; i = e[i].next)
if(e[i].flow > 0 && d[y=e[i].v] + 1 == d[x])
break;
if(i != -1)
{
now[x] = preh[y] = i;
pre[y] = x;
if((x=y) == t)
{
for(f = INF,i=t; i != s; i = pre[i])
if(e[preh[i]].flow < f)
f = e[preh[i]].flow;
ans += f;
do
{
e[preh[x]].flow -= f;
e[preh[x]^1].flow += f;
x = pre[x];
}while(x!=s);
}
}
else
{
if(!--vh[d[x]])
break;
d[x] = n;
for(i=now[x]=head[x]; i != -1; i = e[i].next)
{
if(e[i].flow > 0 && d[x] > d[e[i].v] + 1)
{
now[x] = i;
d[x] = d[e[i].v] + 1;
}
}
++vh[d[x]];
if(x != s)
x = pre[x];
}
}
return ans;
}
//
void build()
{
int i,j;
Init();
source = 0;
sink = 2*n+1;
for(i = 1; i <= n; i++)
addEdge(i,i+n,1);
for(i = 1; i <= n; i++)
{
if(dp[i]==1)
addEdge(source,i,INF);
if(dp[i]==s)
addEdge(i+n,sink,INF);
}
for(i = 1; i <= n; i++)
{
for(j = 1; j < i; j++)
{
if(a[j] < a[i] && dp[j]+1 == dp[i])
addEdge(j+n,i,INF);
}
}
}
int main()
{
int i,j;
while(scanf("%d",&n)!=EOF)
{
s = -1;
for(i = 1; i <= n; i++)
scanf("%d",&a[i]);
for(i = 1; i <= n; i++)
dp[i] = 1;
for(i = 1; i <= n; i++)
{
for(j = 1; j < i; j++)
{
if(a[j] < a[i] && dp[j] + 1 > dp[i])
dp[i] = dp[j] + 1;
}
}
for(i = 1; i <= n; i++)
{
if(s < dp[i])
s = dp[i];
}
printf("%d\n",s);
build();
printf("%d\n",sap(source,sink,sink+1));
}
return 0;
}
分享到:
相关推荐
我们提出了对不相交路径问题的扩展,其中引入了额外的提升边缘以提供路径连接先验。 我们将由此产生的优化问题称为提升的不相交路径问题。 我们通过从整数多商品流和 3-SAT 减少来证明这个问题是 NP 难的。 为了实现...
6 最长递增子序列问题 最多不相交路径 网络最大流 7 试题库问题 二分图多重匹配 网络最大流 8 机器人路径规划问题 (未解决) 最小费用最大流 9 方格取数问题 二分图点权最大独立集 网络最小割 10 餐巾计划问题 线性...
中国科学技术大学博士论文__基于不相交路径技术的可靠网络设计.pdf
算法导论上的算法,用于不相交集合数据结构,按秩合并,路径压缩
该算法以改进的链路状态路由算法为基础,通过在网络拓扑构造过程中引入链路和节点生存时间等参数来提高所选路径的稳定性,同时通过设定影响链路和节点权重的迭代因子来提高多条路径的不相交性,以提高此并行多路径...
寻找最小-最小不相交路径
安全技术-网络信息-AdHoc网络模型下的边不相交路径选择算法.pdf
对有向无环图中具有长度约束的最大不相交路径问题进行研究,该问题是求解图中两点间路径长度为 k的最大不相交路径。为了对该问题进行求解,提出了贪婪搜索算法(GP,greedy path),该算法先将一个有向无环图转化为一棵...
针对最宽不相交路径(WDP)算法计算每个可行路径工作量大而且非常耗时――计算n条路径需要耗费O(n3)次迭代的问题,为了减少算法的复杂度和缩短计算候选路径的时间,提出了一种通过减少可行路径集的数量和限制计算迭代...
给定n个闭区间[ai, bi](1 ),这些区间的并可以表示为一些不相交的闭区间的并。要求在这些表示方式中找出包含不相交区间数目最少的方案。 【输入形式】 输入文件为当前目录下的prz.in。 该文件的第一行包含一个...
不相交多路径路由算法旨在一个端到端的网络中为应用流选择多个路径,且这些路径在瓶颈链路上是彼此不相交的。本文提出的不相交多路径QoS路由(DMQR)算法在Dijkstra最短路径和最短最宽路径(SWP)算法的基础上,能够...
解除不相交路径及其在多目标跟踪中的应用 这是我们ICML 2020论文“解除不相交的路径在多对象跟踪中的应用”的正式实施( ( ,( ,( , ( )[ ]。 我们提供以C ++实现的求解器以及Python包装器。 跟踪器在...
给定x轴上n个闭区间,去掉尽可能少的闭区间,使剩下的闭区间都不相交。 注意:这里,若区间与另一区间之间仅有端点是相同的,不算做区间相交。例如,[1,2]和[2,3]算是不相交区间。 输入格式 第一行一个正整数n...
给定x轴上n个闭区间 去掉尽可能少的闭区间 使剩下的闭区间都不相交 注意:这里 若区间与另一区间之间仅有端点是相同的 不算做区间相交 例如 [1 2]和[2 3]算是不相交区间 输入格式 第一行一个正整数n n< 50 ...
为实现网络多链路故障快速恢复,提出一种基于弧不相交着色树重路由的恢复方法。通过改进着色树机制,建立弧不相交着色树生成模型,提出一种改进的布谷鸟算法,引入动态调整步长操作降低陷入局部极值的概率,优化着色...
题目:1035. 不相交的线方法:最长公共子序列问题。
该方案通过为树中节点提供备用父节点的方式,计算组播源到各个组成员的多条相交路径来代替不相交双树。相交多路径保证了构建成功率并为组播路由提供一定程度的保护。仿真结果表明,该方案构建的组播树以及故障恢复后...
判断通过空间的坐标点确定的选段是否相交,相交的求出交点
在本文中,我们首先根据一般的共形场理论研究了在较小子系统大小范围内激发态的互信息。 然后,我们讨论在相同极限下两个不相交子系统的相对熵。
我们研究弯曲表面上长世界线的接触相互作用,重点是两条世界线相交的平均次数作为其端点的函数。 结果可用于将Wilson循环中采用的路径排序概念从闭合曲线扩展到跨越曲线的曲面内部。 以该表面为弦世界表,可以得到弦...