题目

传送门

思路

• 部分分1（36）

  首先很容易想到一个DP
  \(dp_{i,j}\)表示i号节点的前驱是j
  转移也很简单 \(dp_{i,j}=min_{k=1}^{j-1}dp[k][j-1]+(s[i]-s[j-1])^2\)
  当然要保证可以转移

• 部分分2（64）

  直接对这个DP进行优化

  很容易可以发现对于一个j，我们只需要找到\(min_{i=1}^{j-1}dp[i][j-1]\)就行了

  在用这个minn值往后面转移即可

• 正解

  在Debug的过程中，

  我们可以发现一个规律\(dp_{i,j}<=dp_{i,k}(k<=j)\)

  当然这个结论笔者也不会证明

  但是感性理解

  最后一段最小，

  意味着前面的每一段尽可能小，

  前面的每一段尽可能小也就意味着每一段的平方越小

  即若\(x_1+x_2==y_1+y_2+y_3\)

  使\(x_1,x_2\)尽可能相等，\(y_1,y_2,y_3\)尽可能相等

  \(x_1*x_1+x_2*x_2>=y_1*y_1+y_2*y_2+y_3*y_3\)

  也就是对于一个序列，

  整个序列的最优解的最后一段的长度一定是所有解中长度最小的一段

  考虑怎么向$dp_{i，j} $才会更优

  首先j一定是最接近i的一个j，

  之后我们考虑如何快速的求\(min_{k=1}^{j-1}dp_{j-1,k}\)

  此时的k一定也是最接近j-1的一个k

  我们可以重新定义DP

  \(dp_i\)表示i号节点的前驱节点是谁

  考虑如何转移

  从1号节点到i号节点中最大的能向i号节点转移的dp值

  那么能向\(dp_i\)转移的节点符合什么规律呢

  设转移的节点为k

  \(s_k-s_{dp_k}<=s_i-s_k\)

  \(2*s_k-s_{dp_k}<=s_i\)

  通过这个方程可以很轻易地想到单调队列优化

  某位大犇在出考场的时候一直在吹嘘自己用斜率优化A了这道题，自测好像是0分

  代码

  笔者因为过于懒惰

  其实是太菜

  直接用了__int128

  温馨提醒，CSP不能用__int128

  而且此题有点略微卡常和卡空间

  #include<iostream>
  #include<cstdio>
  #include<queue>
  using namespace std;
  const int mod=(1ll<<30);
  void read(__int128 &x)
  {
      x=0;
      int f=1;
      char c=getchar();
      while('0'>c||c>'9')
      {
          if(c=='-')
              f=-1;
          c=getchar();
      }
      while('0'<=c&&c<='9')
      {
          x=(x<<3)+(x<<1)+c-'0';
          c=getchar();
      }
      x*=f;
  }
  void read(long long &x)
  {
      x=0;
      int f=1;
      char c=getchar();
      while('0'>c||c>'9')
      {
          if(c=='-')
              f=-1;
          c=getchar();
      }
      while('0'<=c&&c<='9')
      {
          x=(x<<3)+(x<<1)+c-'0';
          c=getchar();
      }
      x*=f;
  }
  void read(int &x)
  {
      x=0;
      int f=1;
      char c=getchar();
      while('0'>c||c>'9')
      {
          if(c=='-')
              f=-1;
          c=getchar();
      }
      while('0'<=c&&c<='9')
      {
          x=(x<<3)+(x<<1)+c-'0';
          c=getchar();
      }
      x*=f;
  }
  void write(__int128 x)
  {
      if(x>9)
          write(x/10);
      putchar(x%10+'0');
  }
  struct node
  {
      int p;
      int l;
      int r;
  }fff[100005];
  int n,ty;
  int hea=1;
  int tai=1;
  int now;
  int q[40000005];
  int dp[40000005];
  long long s[40000005];
  int a[40000005];
  int b[40000005];
  __int128 ans;
  __int128 basic=1;
  long long x,y,z,m;
  long long solve_mon(int i)
  {
      return 2*s[i]-s[dp[i]];
  }
  int main()
  {
      read(n);
      read(ty);
      if(ty==0)
      {
          for(int i=1;i<=n;i++)
          {
              read(a[i]);
              s[i]=s[i-1]+a[i];
          }
      }
      else
      {
          read(x);
          read(y);
          read(z);
          read(b[1]);
          read(b[2]);
          read(m);
          for(int i=1;i<=m;i++)
          {
              read(fff[i].p);
              read(fff[i].l);
              read(fff[i].r);
          }
          for(int i=3;i<=n;i++)
              b[i]=(x*b[i-1]%mod+y*b[i-2]%mod+z)%mod;
          for(int j=1;j<=m;j++)
              for(int i=fff[j-1].p+1;i<=fff[j].p;i++)
              {
                  a[i]=(b[i]%(fff[j].r-fff[j].l+1))+fff[j].l;
                  s[i]=s[i-1]+a[i];
              }
      }
      for(int i=1;i<=n;i++)
      {
          while(hea<tai&&solve_mon(q[hea+1])<=s[i])
              hea++;
          dp[i]=q[hea];
          while(hea<tai&&solve_mon(q[tai])>=solve_mon(i))
              tai--;
          q[++tai]=i;
      }
      now=n;
      while(now)
      {
          ans+=basic*(s[now]-s[dp[now]])*((s[now]-s[dp[now]]));
          now=dp[now];
      }
      write(ans);
      return 0;
  }

习题：划分（DP&贪心）

原文：https://www.cnblogs.com/loney-s/p/11908364.html