自动搬运

查看原文

来自洛谷，原作者为

	communist Who Dare Wins !

搬运于2025-08-24 21:58:20，当前版本为作者最后更新于2018-09-18 20:15:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

提供一种无脑$DP$做法

题目中大概有这么些东西：位置，穿鞋，跑路

数据小，那么暴力开数组暴力$DP$吧

设$dp[i][j]$表示穿着鞋子$j$，到达位置$i$是否可行

无脑转移

枚举位置，正在穿哪双鞋，换成哪双走出去，走几步

小的注意事项

1，穿这双鞋不能到这个地方就可以直接跳过，它不能用来转移

2，如果这只鞋不能满足在这个地方死不了，我们就不能穿这双鞋走出去

3，如果走这些步到达的地方，这双鞋不能承受，就不能转移

最后枚举最少穿几双走到$n$即可

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=260;
int n,b,dp[maxn][maxn],f[maxn],s[maxn],d[maxn];
int main()
{
    scanf("%d%d",&n,&b);
    for(int i=1;i<=n;i++)
        scanf("%d",&f[i]);
    for(int i=1;i<=b;i++)
        scanf("%d%d",&s[i],&d[i]);
    dp[1][1]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=b;j++)
            if(dp[i][j])
                for(int k=j;k<=b;k++)
                    if(f[i]<=s[k])
                        for(int l=i+1;l<=min(n,i+d[k]);l++)
                            if(f[l]<=s[k])
                                dp[l][k]=1;
    for(int i=1;i<=b;i++)
        if(dp[n][i])
        {
            printf("%d\n",i-1);
            return 0;
        }
    return 0;
}