洛谷 - P2551 - 华夏60战斗机

https://www.luogu.org/problemnew/show/P2551

首先这道题没有给Hm的最大值，很坑，只能随便开一个100没想到还过了。

观察题目，发现虽然高度可以变化，但是速度是不会下降的。

那么就可以考虑dp，设 \(dp[h][v]\) 表示从开始状态 \(dp[h1][v1]=0\) 到达高度为h，且速度为v的最短的时间。

搞个记忆化搜索就可以了。

需要注意的地方是，不知道什么玄学原因，不能在h为1的时候俯冲，大概是怕撞到地面吧。

要么给h加上上限hm，要么赋值初始化dp为INF标记为禁止状态。

这道题绝对不是蓝色难度，顶多绿色。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF=0x3f3f3f3f;

int h1,v1,h2,v2,dh,hm;

struct Node{

    int cost;

    int preh,prev;

    char op;

    Node(){};

    Node(int _cost,int _preh,int _prev):cost(_cost),preh(_preh),prev(_prev){};

}node[105][7];

bool vis[105][7];

int costtime[105][7][4];

int DP(int h,int v){

    //printf("h=%d v=%d\n",h,v);

    if(vis[h][v]){

        //printf("h=%d v=%d\n",h,v);

        //printf(" ret=%d\n",node[h][v].cost);

        return node[h][v].cost;

    }

    else{

        vis[h][v]=1;

        if(v<v1){

            //printf("h=%d v=%d\n",h,v);

            //printf(" ret=INF\n");

            node[h][v].cost=INF;

            return INF;

        }

        if(h==h1&&v==v1){

            //printf("h=%d v=%d\n",h,v);

            //printf(" ret=0\n");

            node[h][v].cost=0;

            return 0;

        }

        int &cost=node[h][v].cost;

        int &preh=node[h][v].preh;

        int &prev=node[h][v].prev;

        char &op=node[h][v].op;

        cost=INF;

        if(h!=0){

            int tcost=DP(h-1,v)+costtime[h-1][v][1];

            if(tcost<cost){

                preh=h-1;

                prev=v;

                cost=tcost;

                op='R';

            }

        }

        if(v!=0){

            int tcost=DP(h,v-1)+costtime[h][v-1][2];

            if(tcost<cost){

                preh=h;

                prev=v-1;

                cost=tcost;

                op='A';

            }

        }

        if(h>=2&&h+1<=hm){

            int tcost=DP(h+1,v-1)+costtime[h+1][v-1][3];

            if(tcost<cost){

                preh=h+1;

                prev=v-1;

                cost=tcost;

                op='D';

            }

        }

        //printf("h=%d v=%d\n",h,v);

        //printf(" ret=%d\n",cost);

        return cost;

    }

}

void out(int h,int v){

    if(h==h1&&v==v1){

        return;

    }

    else{

        out(node[h][v].preh,node[h][v].prev);

    }

    printf("%c",node[h][v].op);

}

int main() {

    scanf("%d%d%d%d%d%d",&h1,&v1,&h2,&v2,&dh,&hm);

    h1/=dh,h2/=dh,hm/=dh;

    for(int i=0;i<hm;i++){

        for(int j=1;j<=6;j++){

            scanf("%d",&costtime[i][j][1]);

        }

    }

    for(int i=0;i<=hm;i++){

        for(int j=1;j<=5;j++){

            scanf("%d",&costtime[i][j][2]);

        }

    }

    for(int i=2;i<=hm;i++){

        for(int j=1;j<=5;j++){

            scanf("%d",&costtime[i][j][3]);

        }

    }

    memset(vis,0,sizeof(vis));

    printf("%d\n",DP(h2,v2));

    out(h2,v2);

    printf("\n");

}

巴特西

洛谷 - P2551 - 华夏60战斗机 - 简单dp

最新文章

热门文章