UVa 10618 Tango Tango Insurrection

题目

◇题目传送门◆（由于UVa较慢，这里提供一个vjudge的链接）
◇题目传送门（vjudge）◆

题目大意

（题目真长。。。题目描述就不概括了QAQ。。。）

你想学着玩跳舞机。跳舞机的踏板上有四个箭头：上、下、左、右。当舞曲开始时，屏幕上会出现一些箭头，它们会向上移动。当箭头与屏幕顶部的箭头模板重合时，你就需要用脚去踩一下踏板上的相同箭头。不需要踩箭头时，踩箭头不会受到惩罚；而需要踩箭头时，你必须踩一下，哪怕你的脚已经放在那个箭头上了。很多舞曲的速度很快，需要不停地来回倒腾步子。所以你最好写一个程序，来帮助你选择一个轻松的踩踏方式，使得你的能量消耗最少。

为了简单起见，我们将一个八分音符作为一个时间单位。每个时间单位要么需要踩一下箭头，要么不踩任何一个箭头。对于任意时间，你的脚不能放在同一箭头上；每个单位时间只能有一个脚动（移动或者踩箭头），不能跳跃。另外，你不能背对屏幕，即你不能同时将左脚放在右箭头上，右脚放在左箭头上。

当你执行一个动作时（即移动和/或踩箭头），消耗的能量按如下规则计算：

• 若这只脚在上一单位时间内没有任何动作，则消耗1单位能量；
• 若这只脚在上一单位时间内没有移动，则消耗3单位能量；
• 若这只脚在上一单位时间内移动到了相邻箭头，则消耗5单位能量；
• 若这只脚在上一单位时间内移动到了相对的箭头（即上到下，左到右），则消耗7单位能量。

正常情况下，你的左脚不能放到右箭头上（或者反之），但是有一种特殊情况：当你的左脚在上或下箭头时，你可以临时将你的右脚放到左箭头上；但当你的右脚在离开左箭头之前，你的左脚无法移动。同理，当你的右脚在上或下箭头时，你也可以将左脚放到右箭头上。

开始时，你的左脚在左箭头上，右脚在右箭头上。

对于每组测试数据，求出消耗能量最少的移动脚的序列。

思路

（翻译都写了600+。。。QAQ。。。）

我们仔细理一下题目条件可以发现，我们可以按箭头来划分阶段，再记录一下上次左右脚的位置和上次是哪只脚来踩的，就可以进行DP了。

我们首先对箭头进行编号：0-上，1-左，2-右，3-下。至于为什么这样编号，后面再说。

定义状态$f[i][a][b][s]$为已经踩了$i$个箭头，左右脚分别放在$a,b$上，上一次移动的脚集合为$s$（$s=0$：没有脚移动，$s=1$：左脚移动，$s=2$：右脚移动）。

则最终状态为$f[0][1][2][0]$。

若下一步是“..<script type="math/tex" id="MathJax-Element-1666">.</script>”，则有3种决策：左脚移动到一个箭头、右脚移动到一个箭头、两只脚都不动。注意虽然这次移动不会踩箭头，但还是要输出移动的脚。

若下一步是四个箭头之一，则有两种决策：左脚移动到那个箭头上去，右脚移动到那个箭头上去。

注意不要枚举非法的移动方式。

本题细节较多，建议实在想不到的读者结合代码一起看。

正解代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;const int LEFT=1;
const int RIGHT=2;
const int Maxn=70;
const int INF=0x3f3f3f3f;
const char place[]={
   '.','L','R'};
int pos[256];char op[Maxn+5];
int N,dp[Maxn+5][4][4][3];
int p[Maxn+5][4][4][3];int Energy(int a,int ta) {if(a==ta)return 3;//踩一下，消耗能量为3if(a+ta==3)return 7;//移动到相对箭头，消耗能量为7//按照上面的编号，相对箭头之和为3，很容易就判断了移动方向return 5;//相邻箭头，消耗能量为5
}//计算将当前所在的箭头移动到目标箭头所需能量
int Energy(int a,int b,int s,int f,int t,int &ta,int &tb) {ta=a,tb=b;if(f==1)ta=t;else if(f==2)tb=t;//计算目标状态的左右脚位置if(ta==tb)return -1;if(ta==RIGHT&&tb==LEFT)return -1;if(a==RIGHT&&tb!=b)return -1;if(b==LEFT&&ta!=a)return -1;//判断非法状态int e=0;if(f==0)e=0;else if(f!=s)e=1;else {if(f==1)e=Energy(a,ta);else e=Energy(b,tb);}//计算消耗的能量return e;
}
void Update(int i,int a,int b,int s,int f,int t) {int ta,tb;int e=Energy(a,b,s,f,t,ta,tb);if(e<0)return;//非法移动方式，直接返回int cos=dp[i+1][ta][tb][f]+e;if(dp[i][a][b][s]>cos) {
   //更新当前答案dp[i][a][b][s]=cos;p[i][a][b][s]=f*4+t;//将路径压成一个四进制整数存进数组}
}
void Solve() {memset(dp,0,sizeof dp);for(int i=N-1;i>=0;i--)//逆推计算for(int a=0;a<4;a++)//枚举左脚位置for(int b=0;b<4;b++) {
   //枚举右脚位置if(a==b)continue;for(int s=0;s<3;s++) {
   //枚举移动脚的集合dp[i][a][b][s]=INF;if(op[i]=='.') {Update(i,a,b,s,0,0);//这次不动for(int t=0;t<4;t++) {
   //枚举目标箭头Update(i,a,b,s,1,t);//将左脚放到目标箭头上Update(i,a,b,s,2,t);//将右脚放到目标箭头上}} else {Update(i,a,b,s,1,pos[op[i]]);//移动左脚Update(i,a,b,s,2,pos[op[i]]);//移动右脚}}}//输出答案int a=1,b=2,s=0;//初始状态for(int i=0;i<N;i++) {
   //因为是逆推计算，所以顺着输出int f=p[i][a][b][s]/4;int t=p[i][a][b][s]%4;//根据压进的四进制整数求出下一步printf("%c",place[f]);s=f;if(f==1)a=t;else if(f==2)b=t;//状态转移到下一步}puts("");//注意换行
}int main() {#ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifpos['U']=0,pos['L']=1;pos['D']=3,pos['R']=2;//预先存下编号while(true) {scanf("%s",op);if(op[0]=='#')break;N=strlen(op);Solve();}return 0;
}