原题链接

好水的数据，设 $f_{i,j}$ 表示到达第 $i$ 块地砖，此时穿着 $j$ 号鞋子的最小丢弃次数，然后枚举从哪个格子，哪双鞋子的状态到达，注意判断能否走到这个格子。

然后时间复杂度 $O(n^4)$，就这么过了。

#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define ll long long
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define ROF(i,j,k) for(int i=j;i>=k;i--)
int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return x*f;
}
const int N=260;
int n,m,f[N][N],s[N],d[N],a[N];
int main(){n=rd,m=rd;FOR(i,1,n) a[i]=rd;FOR(i,1,m) s[i]=rd,d[i]=rd;memset(f,0x3f,sizeof(f));FOR(i,1,m) f[1][i]=i-1;FOR(i,2,n) FOR(j,1,m){if(s[j]<a[i]) continue;FOR(k,max(1,i-d[j]),i-1){if(s[j]<a[k]) continue;FOR(t,1,j) f[i][j]=min(f[i][j],f[k][t]+j-t);}}int ans=0x3f3f3f3f;FOR(i,1,m) ans=min(ans,f[n][i]);printf("%d\n",ans);return 0;
}