CCPC-WannaFly 2018WC Day1 B.吃豆豆(DP)

题目链接:CCPC-WannaFly 2018WC Day1 B.吃豆豆

题意:

给一个n*m的棋盘,每个格子内有一个数num,当第k秒在这个格子上且num整除k时,可以获得一个糖果,给定起点和终点,问在路上获得至少C个糖果所需要的最短时间,初始时间为0。

题解:

考虑dp,dp(i)(j)(k)=max{dp(i)(j)(k-1),dp(i+1)(j)(k-1),dp(i-1)(j)(k-1),dp(i)(j)(k-1),dp(i)(j+1)(k-1),dp(i)(j-1)(k-1)}+1?

参考代码:

#include<bits/stdc++.h>
using namespace std;
const int inf=0x7f7f7f7f;
int n,m,c;
int mp[15][15],dp[15][15][10200];
int main()
{
    scanf("%d%d%d",&n,&m,&c);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            scanf("%d",&mp[i][j]);
    int sx,sy,ex,ey;
    scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
    memset(dp,-inf,sizeof(dp));
    dp[sx][sy][0]=0;
    for(int k=1; k<=10180; k++)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                if(k%mp[i][j]==0)
                    dp[i][j][k]=max({dp[i-1][j][k-1],dp[i][j+1][k-1],dp[i+1][j][k-1],dp[i][j-1][k-1],dp[i][j][k-1]})+1;
                else
                    dp[i][j][k]=max({dp[i-1][j][k-1],dp[i][j+1][k-1],dp[i+1][j][k-1],dp[i][j-1][k-1],dp[i][j][k-1]});
            }
        }
    }
    int ans=-1;
    for(int i=0; i<=10180; i++)
        if(dp[ex][ey][i]>=c)
        {
            ans=i;
            break;
        }
    printf("%d\n",ans);
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。