[CodeChef] Graph on a Table

CodeChef TBGRAPH

思路

先考虑一个naive的DP,设$f_{i, j}$为一个二元组,记录走到$(i, j)$最多走的步数和方案数。很显然这是$O(n^2\cdot m^2)$的会T得很惨。那么我们很容易发现,对于一个格子$(x, y)$,为了达到最多的步数,一定要从第$x-1$行或者第$y-1$列转移过来,而且能转移过来的一定是一个区间。那么我们可以先预处理出来一个$Left_{i, j}$和一个$Up_{i, j}$,分别表示第$j-1$列能转移到格子$(i, j)$的最小的行,和第$i-1$行能转移到格子$(i, j)$的最小的列。那么DP转移的时候我们就可以对于每行每列维护一个单调队列进行转移了。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

template <typename T> void in(T &_){
  char c=getchar(); _=0; int fl=1;
  while(c<'0'||c>'9') fl=c=='-'?-1:fl, c=getchar();
  while(c>='0'&&c<='9') _=_*10+c-'0', c=getchar(); _*=fl;
}
template <typename T, typename ...A> void in(T &_, A &...a){in(_); in(a...);}

const int MOD=1e9+7;

struct Data{
  int val1, val2; Data(){}
  Data(int val1, int val2) : val1(val1), val2(val2){}
}f[2010][2010];
Data operator +(Data a, Data b){
  if(a.val1==b.val1) return Data(a.val1, (a.val2+b.val2)%MOD);
  if(a.val1>b.val1)  return a; return b;
}
Data operator +=(Data &a, Data b){return a=a+b;}

struct Rec{
  int x1, y1, x2, y2;
}r[500010];
int N, M, Q, Left[2010][2010], Up[2010][2010], pos[2010];

struct Priority_Queue{
  int h, t, w[2010], cnt[2010];
  Data a[2010];
  void init(){
    h=1, t=0;
    std::fill(cnt, cnt+std::min(N, M)+1, 0);
  }
  void push(int x, Data y){
    while(h<=t && a[t].val1<y.val1)
      cnt[a[t].val1]=(cnt[a[t].val1]-a[t].val2)%MOD, t--;
    cnt[y.val1]=(cnt[y.val1]+y.val2)%MOD;
    a[++t]=y; w[t]=x;
  }
  Data query(int x){
    while(h<=t && w[h]<x)
      cnt[a[h].val1]=(cnt[a[h].val1]-a[h].val2)%MOD, h++;
    return Data(a[h].val1+1, cnt[a[h].val1]);
  }
}R[2010], C[2010];

int main(){
  int T; in(T);
  while(T--){
    in(N, M, Q);
    for(int i=1; i<=N; i++) 
      for(int j=1; j<=M; j++)
        Left[i][j]=Up[i][j]=0;
    for(int i=1; i<=Q; i++)
      in(r[i].x1, r[i].y1, r[i].x2, r[i].y2);
    std::sort(r+1, r+Q+1, [](Rec a, Rec b){return a.x1<b.x1;});
    std::fill(pos+1, pos+M+1, 0);
    for(int i=1; i<=Q; i++)
      for(int j=r[i].y1+1; j<=r[i].y2; j++){
        pos[j]=std::max(pos[j], r[i].x1+1);
        while(pos[j]<=r[i].x2)
          Left[pos[j]++][j]=r[i].x1;
      }
    std::sort(r+1, r+Q+1, [](Rec a, Rec b){return a.y1<b.y1;});
    std::fill(pos+1, pos+N+1, 0);
    for(int i=1; i<=Q; i++)
      for(int j=r[i].x1+1; j<=r[i].x2; j++){
        pos[j]=std::max(pos[j], r[i].y1+1);
        while(pos[j]<=r[i].y2)
          Up[j][pos[j]++]=r[i].y1;
      }
    for(int i=1; i<=N; i++)
      for(int j=1; j<=M; j++)
        f[i][j]=Data(1, 1);
    for(int i=1; i<=N; i++) R[i].init();
    for(int i=1; i<=M; i++) C[i].init();
    for(int i=1; i<=N; i++)
      for(int j=1; j<=M; j++){
        R[i].push(j, f[i][j]);
        C[j].push(i, f[i][j]);
        if(i<N && j<M && Up[i+1][j+1]){
          f[i+1][j+1]+=R[i].query(Up[i+1][j+1]);
          f[i+1][j+1]+=C[j].query(Left[i+1][j+1]);
          if(f[i][j].val1+1==f[i+1][j+1].val1)
            f[i+1][j+1].val2=(f[i+1][j+1].val2-f[i][j].val2)%MOD;
        }
      }
    Data ans=Data(0, 0);
    for(int i=1; i<=N; i++)
      for(int j=1; j<=M; j++) ans+=f[i][j];
    printf("%d %d\n", ans.val1, (MOD+ans.val2)%MOD);
  }
  return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注