题解 P5033 【跑酷】
南城忆潇湘
·
·
题解
解法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]
第三种，这个格子为粘液块的时候（最恶心的就是这种情况）
预计得分: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;
}
```