首页 > 代码库 > NYOJ740

NYOJ740

2024-08-06 06:15:33   215人阅读

题目连接：http://acm.nyist.net/JudgeOnline/talking.php?pid=740

来看思路：

首先我们先设dp[i][j][k] 为第i个点的时候左脚在j点右脚在k点

先固定一只脚的位置j,第i次踩踏后，状态为dp[i][j][a[i]]或者dp[i][a[i]][j],其中a[i]表示第i个输入

x=dp[i-1][k][j]+cost[k][a[i]]; 是通过k踩过来的，cost[k][a[i]]表示k->a[i]的花费。

y=dp[i-1][j][k]+cost[k][a[i]]; 是通过k踩过来的，cost[k][a[i]]表示k->a[i]的花费。

dp[i][j][a[i]]=dp[i][a[i]][j]=min(x,y)；

#include<stdio.h>#include<string.h>#include<math.h>int dp[10001][6][6];int a[10001];int cost[6][6]={{1,2,2,2,2},{0,1,3,4,3},{0,3,1,3,4},{0,4,3,1,3},{0,3,4,3,1}};int main(){    int i,j,k,n,ans,x,y,t;    while(scanf("%d",&t)&&t!=0)    {        a[1] = t;        for(n = 2;;n++)        {            scanf("%d",&a[n]);            if(!a[n])            {                break;            }        }        for(i = 0;i <= n;i++)            for(j = 0;j < 5;j++)                for(k = 0;k < 5;k++)                    dp[i][j][k] = 100000005;        dp[0][0][0] = 0;        ans = 100000005;        for(i = 1;i < n;i++)        {            for(j = 0;j < 5;j++) //先确定一只脚不动            {                if(j == a[i])continue;                x = y = 100000005;                for(k = 0;k < 5;k++)  //左脚动                {                    if(k != j||k + j == 0)                    {                        if(x > dp[i - 1][k][j] + cost[k][a[i]])                        {                            x = dp[i - 1][k][j] + cost[k][a[i]];                        }                    }                }                for(k = 0;k < 5;k++)  //右脚动                {                    if(k != j||k + j == 0)                    {                        if(y > dp[i - 1][j][k] + cost[k][a[i]])                        {                            y = dp[i - 1][j][k] + cost[k][a[i]];                        }                    }                }                if(x > y)x = y;                dp[i][a[i]][j] = dp[i][j][a[i]] = x;   //左脚和右脚是可以相互转换的                if(ans > dp[n - 1][j][a[i]])ans = dp[n - 1][j][a[i]];            }        }        printf("%d\n",ans);    }    return 0;}

 

NYOJ740


联系
我们