记录编号 571882 评测结果 AAAAAAAAAA
题目名称 [USACO Feb18 Silver]Snow Boots 最终得分 100
用户昵称 Gravatar00000 是否通过 通过
代码语言 C++ 运行时间 0.000 s
提交时间 2022-06-25 19:22:36 内存使用 0.00 MiB
显示代码纯文本
#include<bits/stdc++.h>
#define long long ll
using namespace std;
int n,b,a[200000],d[200000],l[200000];
int f[3000][3000];//第一维 靴子,第二维 位置
int main(){
freopen("snowboots_silver_18feb.in","r",stdin);
freopen("snowboots_silver_18feb.out","w",stdout);
cin>>n>>b;
f[1][1]=1;
for(int q=1;q<=n;q++) cin>>a[q];
for(int q=1;q<=b;q++) cin>>d[q]>>l[q];
for(int q=1;q<=b;q++)
{
    for(int w=1;w<=n;w++)
    {
        if(f[q-1][w]==1) f[q][w]=2;
        if(f[q-1][w]>0&&d[q]>=a[w]) f[q][w]=1;
        if(f[q][w]==1)
        {
            for(int e=1;e<=l[q];e++)
            {
                if(d[q]>=a[w+e]) f[q][w+e]=1;
            }
        }
    }
}
int k;
for(int q=1;q<=b;q++)
{
    if(f[q][n]==1)
    {
        k=q;
        break;
     } 
}
cout<<k-1;
return 0;
}