在一个 $N \times N$ 的方阵里，小明在左上角（第一行第一列），要去右下角（第 $N$ 行第 $N$ 列）。小明每次可以选择上、下、左、右四个方向移动一格，直到移动到右下角。每一个格子上有一个整数，一条路线的简单度是路径上格子里的最大整数减掉最小整数。

小明希望找到一条最简单的路线，也就是简单度最小的路线。

$2 \le N \le 100$，$0 \le A_{i,j} \le 110$。

73 分 WA（二分答案简单度然后枚举最小值和最大值，用 BFS 判断是否可行）：

#include<cstdio>
#include<queue>
using namespace std;
const int N=110,dx[5]={0,1,-1,0,0},dy[5]={0,0,0,1,-1};
int n,mx,a[N][N]; bool vis[N][N]; 
bool bfs(int l,int r) {//最小 l，最大 r
  for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++) vis[i][j]=false;
  queue<pair<int,int> >q; q.push(make_pair(1,1)); vis[1][1]=true;
  while(!q.empty()) {
    pair<int,int> p=q.front(); q.pop();
    if(p.first==n&&p.second==n) return true;
    for(int i=1;i<=4;i++) {
      int xx=p.first+dx[i],yy=p.second+dy[i];
      if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&a[xx][yy]>=l&&a[xx][yy]<=r&&!vis[xx][yy]) {
        q.push(make_pair(xx,yy));
        vis[xx][yy]=true;
      }
    }
  }
  return false;
}
bool check(int d) {
  for(int i=0;i<=mx-d;i++)//枚举最小和最大
    if(bfs(i,i+d)) return true;
  return false;
}
int main() {
  scanf("%d",&n);
  for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++) {
      scanf("%d",&a[i][j]);
      if(a[i][j]>mx) mx=a[i][j];
    }
  int l=0,r=mx,ans;
  while(l<=r) {//二分答案简单度
    int mid=l+r>>1;
    if(check(mid)) ans=mid,r=mid-1;
    else l=mid+1;
  }
  return printf("%d",ans),0;
}

---

为了美观，京南路上种上了绿化带，你可以把绿化带看成一维的数轴，长为一个偶数 $L$。为了保持绿化带的绿叶长青，需要经常浇水。用来浇水的那个浇水机可以双向浇水，并且有确定的射程，射程不短于 $A$ 并且不长于 $B$。它所在位置的两边射程内，都属于它的浇灌区域。现在要求绿化带的每一个区域都被浇灌到，而且浇水机的浇灌区域不允许重叠，并且任何一个浇水机都不能把水浇到绿化带外面。

绿化带上会放 $N$ 块招牌，第 $i$ 块招牌的位置在 $[S_i,E_i]$，不同的招牌的位置可以重叠。要求每个招牌仅被一个浇水机浇灌。

求最少需要的浇水机数目。无解输出 $-1$。

$1 \le L \le 10^6$，$1 \le A \le B \le 1000$，$1 \le N \le 1000$，$1 \le S_i \le E_i \le L$。

30 分 WA。

设 $dp_i$ 代表浇水机又端点为 $i$ 的最少浇水机数量，答案就是 $dp_l$。转移方程：

$dp_i=\min\limits_{2a \le i-j \le 2b} \{dp_j\} +1$

招牌的话即所有的 $[S_i+1,E_i-1]$ 不能作为右端点，用差分预处理。

用了单调队列优化 dp。

#include<cstdio>
using namespace std;
const int L=1e6+10,INF=0x7f7f7f7f; int dp[L],d[L],q[L];
int main() {
  int n,l,a,b,head=1,tail=1; scanf("%d %d %d %d",&n,&l,&a,&b);
  for(int i=1,s,e;i<=n;i++) scanf("%d %d",&s,&e),d[s+1]+=INF,d[e]-=INF;
  for(int i=1;i<=l;i++) dp[i]=dp[i-1]+d[i];
  for(int i=2*a;i<=l;i++) {
    while(head<tail&&dp[i-2*a]<=dp[q[tail-1]]) tail--;
    q[tail++]=i-2*a;
    while(head<tail&&i-q[head]>2*b) head++;
	if(dp[i]==INF) continue;
    dp[i]=dp[q[head]]+1;
  }
  if(dp[l]>=INF) printf("-1");
  else printf("%d",dp[l]);
  return 0;
}