首页 > 其他分享 >洛谷 P2766【网络流】【线性DP】

洛谷 P2766【网络流】【线性DP】

时间:2022-10-11 13:00:07浏览次数:85  
标签:洛谷 int delta dep && ans return P2766 DP

摘自网络流 \(24\) 题官方题解。

第一问:直接 \(O(n^2)\) DP 求解最长不下降子序列即可。

第二问:

使用类似于 酒店之王 的思想,将点 \(i\) 拆成两个点 \(i_1\),\(i_2\)。然后 \(i_1\to i_2\) 的容量为 \(1\)。

如果有 \(i\in [1,n]\),\(f_i = 1\),那么 \(s\to i_1\) 连一条容量为 \(1\) 的边。

如果有 \(i\in[1,n]\),\(f_i = 最长不下降子序列的长度\),那么 \(i_2\to t\) 连一条容量为 \(1\) 的边。

如果是最长不下降子序列的转移,那么从 \(i_2\to j_1\) 的容量为 \(1\)。

然后求网络最大流即可。

第三问:

取消第一个点和最后一个点的流量限制即可。

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 2e5 + 10;
int a[N], f[N], dep[N];
int n, s, t;
const int inf = 1e9 + 154;

struct edge
{
  int e, f, opt;
  edge() {}
  edge (int a, int b)
  {
    this->e = a, this->f = b;
  }
};
vector <edge> z[N];
vector <edge> ty[N];

void add(int s, int e, int f)
{
  z[s].push_back(edge(e, f));
  z[e].push_back(edge(s, 0));
  int s1 = z[s].size() - 1, s2 = z[e].size() - 1;
  z[s][s1].opt = s2;
  z[e][s2].opt = s1;
}

bool bfs()
{
  queue <int> q;
  memset (dep, 0, sizeof dep);
  dep[s] = 1;
  q.push(s);
  while (q.size())
  {
    int p = q.front();
    q.pop();
    for (auto &[r, f, g] : z[p])
      if (f && !dep[r])
      {
        dep[r] = dep[p] + 1;
        q.push(r);
        if (r == t)
          return true;
      }
  }
  return false;
}

int dfs(int p, int f)
{
  if (p == t)
    return f;
  int ans = 0;
  for (int i = 0; i < z[p].size() && f; i ++)
  {
    int q = z[p][i].e;
    int fx = z[p][i].f;
    if (fx && dep[p] + 1 == dep[q])
    {
      int delta = dfs(q, min(f, fx));
      z[p][i].f -= delta;
      z[q][z[p][i].opt].f += delta;
      f -= delta;
      ans += delta;
    }
  }
  if (!ans)
    dep[p] = 0;
  return ans;
}

int dinic()
{
  int ans = 0;
  while (bfs())
    ans += dfs(s, inf);
  return ans;
}

signed main()
{
  cin >> n;
  for (int i = 1; i <= n; i ++)
    cin >> a[i];
  if (n == 1)
  {
    cout << "1\n1\n1\n";
    return 0;
  }
  for (int i = 1; i <= n; i ++)
  {
    f[i] = 1;
    for (int j = 1; j < i; j ++)
      if (a[j] <= a[i])
        f[i] = max(f[i], f[j] + 1);
  }
  int k = *max_element(f + 1, f + n + 1);
  cout << k << '\n';
  s = 2001, t = 2002;
  for (int i = 1; i <= n; i ++)
    if (f[i] == 1)
      add(s, i, 1);
  for (int i = 1; i <= n; i ++)
    if (f[i] == k)
      add(i + n, t, 1);
  for (int i = 1; i <= n; i ++)
    add(i, i + n, 1);
  for (int i = 2; i <= n; i ++)
    for (int j = 1; j < i; j ++)
      if (a[i] >= a[j] && f[j] + 1 == f[i])
        add(j + n, i, 1);
  for (int i = 1; i <= 2002; i ++)
    ty[i] = z[i];
  cout << dinic() << '\n';
  for (int i = 1; i <= 2002; i ++)
    z[i] = ty[i];
  add(1, n + 1, inf);
  add(s, 1, inf);
  if (f[n] == k)
  {
    add(n + n, t, inf);
    add(n, n + n, inf);
  }
  // for (int i = 1; i <= 2002; i ++)
  //   z[i].clear();
  // for (int i = 1; i <= n; i ++)
  //   if (f[i] == k)
  //   {
  //     if (i != 1 && i != n)
  //       add(s, i, 1);
  //     else
  //       add(s, i, inf);
  //   }
  // for (int i = 1; i <= n; i ++)
  //   if (f[i] == 1)
  //   {
  //     if (i != 1 && i != n)
  //       add(i + n, t, 1);
  //     else
  //       add(i + n, t, inf);
  //   }
  // for (int i = 1; i <= n; i ++)
  //   if (i != 1 && i != n)
  //     add(i, i + n, 1);
  //   else
  //     add(i, i + n, inf);
  // for (int i = 2; i <= n; i ++)
  //   for (int j = 1; j < i; j ++)
  //     if (a[i] >= a[j] && f[j] + 1 == f[i])
  //       add(i + n, j, 1);
  cout << dinic() << '\n';
  return 0;
}

标签:洛谷,int,delta,dep,&&,ans,return,P2766,DP
From: https://www.cnblogs.com/lxylluvio/p/luogu2766.html

相关文章

  • linux包管理器rpm和dpkg的使用说明
    软件包:开源软件刚开始只提供打包好的源代码文件(例如:.tar.gz),用户需要自己使用编译器编译后才能使用。Debian诞生时,管理工具dpkg也就应运而生,可用来管理deb后缀的"包"......
  • 洛谷 P8572【暴力】【根号分治】
    根号分治。需要进行分类讨论:当\(n\lek\)的时候,可以进行暴力\(\#1\):暴力求出数组所有区间的最大值。(需要使用前缀和)否则,可以使用一个叫做“记忆化”的鬼玩意。如......
  • 洛谷P4320 道路相遇(LCA+圆方树)
    题目链接:https://www.luogu.com.cn/problem/P4320道路相遇题目描述在H国的小w决定到从城市$u$到城市$v$旅行,但是此时小c由于各种原因不在城市$u$,但是小c决......
  • Optimal Partition (线段树优化DP)
    给定一个数组 a,(1≤n≤5×105),你需要将其分割为若干个连续的子数组,使所有子数组的价值总和最大。定义价值是:r-l+1,和>00,和=0-(r−l+1),和<0;思路:首先这道题初......
  • 矩阵类优化——动态dp
    Idea主要指用矩阵维护带修改的dp问题的方法,一般会用到数据结构来维护矩阵。矩阵的用法具体见矩阵加速优化dp.下面主要根据例题讲解。Problem1.P4719【模板】"......
  • expdp备份集直接导出到asm磁盘组
    文档课题:expdp备份集直接导出到asm磁盘组.系统:rhel8.464位数据库:oracle19.1264位+asm+单实例+多租户操作过程:ASMCMD>pwd+data/orclcdbASMCMD>mkdirrmanbakASMC......
  • 洛谷 P3488 [POI2009]LYZ-Ice Skates 题解
    错解每次跑二分图匹配,时间复杂度显然爆炸。时间复杂度:我被杀手皇后摸过了正解引入Hall定理:设二分图中\(G=<V_1,V_2,E>,|V_1|\le|V_2|\),则G中存在\(V_1\)到......
  • 洛谷 P3067 [USACO12OPEN]Balanced Cow Subsets G 折半搜索
    题目https://www.luogu.com.cn/problem/P3067思路考虑折半搜索,第一个dfs对[1,n/2]的数进行分组,+代表第一组,-代表第二组,并计算两组总和的情况方案数\(a_i\)。第二个dfs......
  • 洛谷 P3530 / bzoj2788【tarjan】【差分约束】
    判断是否有解可以使用差分约束。求解赛车手的成绩的取值可以使用Floyd。但是\(O(n^3)\)会TLE。可以先进行一次缩点。然后进行Floyd求出每一个连通块内的最长路径......
  • 洛谷 P5194 [USACO05DEC]Scales S 折半搜索
    题目https://www.luogu.com.cn/problem/P5194思路\(n\leq1000\)的范围很吓人,但是按照【每个砝码的质量至少等于前面两个砝码的质量的和】的规则,打表可知n在50时总重量......