﻿ UVA1291----Dance Dance Revolution----3维DP-CSS_网页制作-脚本宝典

# UVA1291----Dance Dance Revolution----3维DP

## UVA1291----Dance Dance Revolution----3维DP

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+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;
}
```

Tag：

﻿
<