Dance Dance Revolution

时间：2023-03-08 21:22:56

今天我们来讲 Dance Dance Revolution这题

本题原网址

注意本题为多组输入输出，直到输入单个零而止(题面有点小问题)

很明显，此题为一道动态规划题（请不要妄想用贪心算法过这题，尽管你可能可以过样例，但是面对你的依然是WA），首先要存一个cost数组，用于存储从i号点到j号点的花费，存储过程如下

int cost[5][5];

void cost_put()

{

    for(int i=0;i<=4;i++)cost[i][i]=1;

    for(int i=1;i<=3;i++)cost[i][i+1]=cost[i+1][i]=3;

    cost[4][1]=cost[1][4]=3,cost[3][1]=cost[1][3]=cost[2][4]=cost[4][2]=4;

    for(int i=1;i<=4;i++)cost[0][i]=cost[i][0]=2;

}

存储完后，就该想想状态的描述，很显然，我们不仅需要描述他左脚和右脚的位置，还需要描述已经踩到了第几个音符。

因此要开一个三维的dp数组，\(dp[i][j][k]\)表示踩完第i个后，左脚在i号点，右脚在j号点，所需的最小花费。

想好了状态后，接着初始化，过程如下

    scanf("%d",&x);

    for(int i=1;i<=100000;i++)

        for(int j=0;j<=4;j++)

            for(int k=0;k<=4;k++)

                dp[i][j][k]=1e9;

    dp[0][0][0]=0;dp[1][x][0]=dp[1][0][x]=2;

该想转移方程了，在纸上画一画，很容易想到如下的转移方程（注意以下两个方程的细微差别）

dp[tot][x][i]=min(dp[tot-1][j][i]+cost[x][j],dp[tot][x][i]);

//正准备踩第i个，此时左脚踩到要踩的点，右脚踩在i号点上，所需的最小花费

dp[tot][i][x]=min(dp[tot-1][i][j]+cost[x][j],dp[tot][i][x]);

//正准备踩第i个，此时右脚踩到要踩的点，左脚踩在i号点上，所需的最小花费

想到这里已经没有什么可以难倒你了，但是有以下几点要注意：

2.\(dp\)数组和\(ans\)变量的初始值一定要设成极大值，因为要取最小值（算最小的花费值当然是取最小值）

3.最后\(ans\)一定取值时要在除去\(dp[tot][0][0],dp[tot][1][1],dp[tot][2][2],dp[tot][3][3],dp[tot][4][4]\)（\(tot\)为歌曲总长度）这几个状态的答案，这些状态违反了题目中两脚不可以同时踩在同一点的规则

完整代码：

#include<bits/stdc++.h>

using namespace std;

int x,cost[5][5],dp[100010][5][5],tot=1,ans=1e9;

void cost_put()

{

    for(int i=0;i<=4;i++)cost[i][i]=1;

    for(int i=1;i<=3;i++)cost[i][i+1]=cost[i+1][i]=3;

    cost[4][1]=cost[1][4]=3,cost[3][1]=cost[1][3]=cost[2][4]=cost[4][2]=4;

    for(int i=1;i<=4;i++)cost[0][i]=cost[i][0]=2;

}

int main()

{

    cost_put();

    while(true)

	{

		scanf("%d",&x);

		if(x==0)break;

		tot=1;ans=1e9;

	    for(int i=1;i<=100000;i++)

	        for(int j=0;j<=4;j++)

	            for(int k=0;k<=4;k++)

	                dp[i][j][k]=1e9;

	    dp[0][0][0]=0;dp[1][x][0]=dp[1][0][x]=2;

	    //初始化

	    while(x!=0)

	    {

	        scanf("%d",&x);

	        tot++;

	        for(int i=0;i<=4;i++)

	            for(int j=0;j<=4;j++)

	                 dp[tot][x][i]=min(dp[tot-1][j][i]+cost[x][j],dp[tot][x][i]);

	        for(int i=0;i<=4;i++)

	            for(int j=0;j<=4;j++)

	                dp[tot][i][x]=min(dp[tot-1][i][j]+cost[x][j],dp[tot][i][x]);

	    }

	    //转移

	    tot--;

	    for(int i=0;i<=4;i++)

	        for(int j=0;j<=4;j++)

	            if(i!=j)ans=min(ans,dp[tot][i][j]);

	    //统计答案

	    printf("%d\n",ans);

	}

    return 0;

}

相关文章