【loj2567】【APIO2016】划艇

标签：std   离散   com   time   c++   sum   can   fine   long   

题目

\(N\)个位置，每个位置要么不选，要么选\([ a_i, b_i ]\)中的一个数；

问最后的单调上升序列(mod 1e9+7)有多少种；

\(1 \le N \le 500\)

题解

• orz abclzr

• 直接\(dp\)最后一位是什么数字的话只能得到31分

• 将数字离散化分段，第\(i\)段为\([l_i,r_i)\)，设\(f_{i,j}\)表示第i个位置选的数字在第j段的方案数(第0段表示没有)
  \[ f_{i,j} \ = \sum_{k=0}^{i-1} \sum_{l=0}^{j-1} f_{k,l} \times cal(k+1,i,j) \ans = \sum_{i=1}^n \sum_{j=1}^m f_{i,j} \\]

• 其中$cal(l,r,x) \(表示\)[l,r)$都不选或者选在第j段并且单调上升的方案数

• 设 $ [ l,r) $ 这里面有 $ S $ 个包含x区间，x区间的长度为 $ L $　
  \[ cal(l,r,x) = \sum_{i=0}^{S}(^S_i)(^L_{i+1}) = \sum_{i=0}^{S}(^S_{S-i})(^L_{i+1}) \思考组合意义：左边选S-i个再在右边选i+1个相当与一起选S+1个\cal(l,r,x) = (^{S+L}_{S+1}) \\]

• 前缀和优化dp即可：\(O(n^3)\)　　

  #include
  #define ll long long 
  using namespace std;
  const int N=1010,mod=1e9+7;
  int n,tot,sub[N],L[N],R[N],ny[N],l[N],f[N][N];
  void inc(int&x,int y){x+=y;if(x>=mod)x-=mod;}
  int main(){
  //    freopen("boat.in","r",stdin);
  //    freopen("boat.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i

  //菜兔兔写的部分分
  #include
  #define pb push_back
  using namespace std;
  const int N=510,M=2000010,mod=1e9+7;
  int n,a[N],b[N],len[N],sub[M],tot;
  int f[M],g[M];
  void inc(int&x,int y){x+=y;if(x>=mod)x-=mod;}
  int main(){
  //    freopen("boat.in","r",stdin);
  //    freopen("boat.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i

【loj2567】【APIO2016】划艇

标签：std   离散   com   time   c++   sum   can   fine   long   

原文地址：https://www.cnblogs.com/Paul-Guderian/p/10840912.html