P4265 【[USACO18FEB]Snow Boots S】

communist · 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;
}