来源：自学PHP网 时间：2015-04-14 14:51 作者： 阅读:次
[导读] 题目意思：跳舞机中间为0上左下右分别为1，2，3，4然后从0到其他消费2相邻的移动消费3原地踏步消费1相对移动消费2给你一串舞步，初始双脚站在中间，问你跳完的最小消耗思路：简单...
|
题目意思：
跳舞机
中间为0
上左下右分别为1，2，3，4
然后从0到其他消费2
相邻的移动消费3
原地踏步消费1
相对移动消费2
给你一串舞步，初始双脚站在中间，问你跳完的最小消耗
思路：
简单的区间DP，但是自己写了好久啊，囧
令f[n][i][j]表示第n步时的左右脚分别为i,j的最小步数
则装态转移方程：
如果f(i, j, s), (0<=j<=4)状态可达
则可推出下一个的状态
f(i+1, j, s) = f(i, j, s) + 1; // 停在当前不动
f(i+1, next, s) = min{ f(i, j, s) + check(j, next)}
f(i+1, j, next) = min{ f(i, j, s) + check(s, next)}
同理，如果f(i, s, j), (0<=j<=4)状态可达
也可推出下一个状态:
f(i+1, s, j) = f(i, j, s) + 1; // 停在原地不动
f(i+1, next, j) = min{ f(i, s, j) + check(s, next)}
f(i+1, s, next) = min{ f(i, s, j) + check(j, next)}
推了很久啊
下面上代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[20000][5][5];
const int inf = 0x3f3f3f3f;
int check(int st,int ed)
{
if(st==ed)
return 1;
if(st==0 || ed==0)
return 2;
if(st==1)
{
if(ed == 2 || ed==4)
return 3;
return 4;
}
if(st==2)
{
if(ed == 1 || ed==3)
return 3;
return 4;
}
if(st == 3)
{
if(ed==2 || ed==4)
return 3;
return 4;
}
if(st==4)
{
if(ed == 1|| ed==3)
return 3;
return 4;
}
}
int main()
{
int tmp;
while(1)
{
int cnt = 0;
memset(dp,inf,sizeof(dp));
dp[0][0][0] = 0;
int tmp2=0;
while(1)
{
scanf("%d",&tmp);
if(tmp == 0)
break;
cnt++;
for(int i=0;i<=4;i++)
{
dp[cnt][i][tmp2] = min(dp[cnt][i][tmp2],dp[cnt-1][i][tmp2]+1);
dp[cnt][tmp2][i] = min(dp[cnt][tmp2][i],dp[cnt-1][tmp2][i]+1);
dp[cnt][tmp][i] = min(dp[cnt][tmp][i],dp[cnt-1][tmp2][i]+check(tmp2,tmp));
dp[cnt][tmp2][tmp] = min(dp[cnt][tmp2][tmp],dp[cnt-1][tmp2][i]+check(i,tmp));
dp[cnt][tmp][tmp2] = min(dp[cnt][tmp][tmp2],dp[cnt-1][i][tmp2]+check(i,tmp));
dp[cnt][i][tmp] = min(dp[cnt][i][tmp],dp[cnt-1][i][tmp2]+check(tmp2,tmp));
}
tmp2 = tmp;
}
if(cnt==0)
break;
int ans = inf;
for(int i=0;i<=4;i++) if(i!=tmp2)
ans = min(dp[cnt][tmp2][i],ans);
for(int i=0;i<=4;i++) if(i!=tmp2)
ans = min(dp[cnt][i][tmp2],ans);
cout<<ans<<endl;
}
return 0;
}
|
自学PHP网专注网站建设学习,PHP程序学习,平面设计学习，以及操作系统学习
京ICP备14009008号-1@版权所有www.zixuephp.com
网站声明：本站所有视频，教程都由网友上传，站长收集和分享给大家学习使用，如由牵扯版权问题请联系站长邮箱904561283@qq.com
