【网络流与线性规划24题】最长递增子序列问题

这题听说数据有误。。无解了

首先可以dp出以每一位结束的最长递增子序列dp[i]

那么建一张二分图:把每个数拆成两个点,若dp[i]==1,则从S向左边的i连一条边;若dp[i]==ans1,则从左边的i向T连一条边;若dp[i]+1==dp[j]则从左边的i向右边的j连一条边。从右边的i向左边的i连一条边。流量全部为1。这样第二问就求出来了。

第三问:如果一开始存在,将S到左边的1和右边的n到T的边的流量改为正无穷。然后再跑一遍。

说点什么

  Subscribe  
提醒