自动搬运

查看原文

来自洛谷，原作者为

	南城忆潇湘 今天又是摸鱼的一天

搬运于2025-08-24 22:06:24，当前版本为作者最后更新于2018-11-14 07:00:08，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

解法1：
我有信仰，我是MC玩家，输出qwq，预计得分10分。

解法2:
我会模拟，直接模拟，要么走4格，要么走3远一高，要么摔下去。预计得分50分。（qwq这都有50分惹）

解法3：
我会广搜，直接广搜来搞。根据自己愿意模拟的程度来决定得分。预计得分20-80分。（我也不知道为啥有这么高分）

解法4：
我会dp,$f[i][j]$表示到第$i$格方块，有$j$格血时候的最小跳跃次数。然后进行状态转移。
第一种，这个格子为普通方块的时候：
$f[i][j]=f[i-x][j]+1$
第二种，这个格子比前面格子高的时候:
$f[i][j]=f[i-x][j+shuailuo]$
第三种，这个格子为粘液块的时候（最恶心的就是这种情况）
$f[i+x2][j]=f[i-x1][j+shuailuo']$（当且仅当前面格子与这个格子差大于这个格子与后面格子高度差的$3/5$的时候）
预计得分:100分

代码：（100pts）

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
struct block{
    int x,y;
    char p;
}a[10001];
int f[10001][21];
bool pd;
int shuailuo(int h){
    h=(h<=0)?-h:h;
    if(h<=3)	return 0;
    return h-3;
}
int main(){
    int n;
    cin>>n;
    memset(f,127,sizeof(f));
    for(int i=1;i<=n;i++)
        scanf("%d %d %c",&a[i].x,&a[i].y,&a[i].p);
    f[1][20]=0;
    for(int i=1;i<n;i++){	
        pd=1;
        for(int k=1;k<=20;k++)
            if(f[i][k]!=f[0][0])	pd=0;
        if(pd==1){
            cout<<"qwq";
            return 0;
        }
        for(int j=i+1;j<=n;j++){
            int h=a[j].y-a[i].y,w=a[j].x-a[i].x;//up
            if(w>4)	break;
            if((h>=0&&h<=1&&w>0&&w<=3)||(h==0&&w==4))
                for(int k=1;k<=20;k++)
                    f[j][k]=min(f[j][k],f[i][k]+1);
        }
        int h=a[i+1].y-a[i].y,w=a[i+1].x-a[i].x;
        if(h<0&&w==1){
              if(a[i+1].p=='P')
                   for(int k=shuailuo(h)+1;k<=20;k++)	
						f[i+1][k-shuailuo(h)]=min(f[i+1][k-shuailuo(h)],f[i][k]);
               if(a[i+1].p=='Z'||a[i+1].p=='N')
                    for(int k=1;k<=20;k++)	
                        f[i+1][k]=min(f[i+1][k],f[i][k]);
            } 
		if(a[i].p=='N'){
		int hl=a[i-1].y-a[i].y,wl=a[i].x-a[i-1].x,h=a[i+1].y-a[i].y;//down
            if(hl<=0||wl!=1)	continue;
            if(hl*3/5>=h){
                for(int k=shuailuo(hl*3/5-h)+1;k<=20;k++)
                    f[i+1][k-shuailuo(hl*3/5-h)]=min(f[i+1][k-shuailuo(hl*3/5-h)],f[i][k]);
            }
        }
    }
    int ans=999999;
    for(int k=1;k<=20;k++)
        ans=min(f[n][k],ans);
    if(ans==999999)	cout<<"qwq";
    else cout<<ans;
    return 0;
}