UVA 10618 Tango Tango Insurrection

https://vjudge.net/problem/UVA-10618

题目

你想学着玩跳舞机。跳舞机的踏板上有4个箭头:上、下、左、右。当舞曲开始时,屏幕上会有一些箭头往上移动。当向上移动箭头与顶部的箭头模板重合时,你需要用脚踩一下踏板上的相同箭头。不需要踩箭头时,踩箭头并不会受到惩罚,但当需要踩箭头时,必须踩一下,哪怕已经有一只脚放在了该箭头上。很多舞曲的速度快,需要来回倒腾步子,所以最好写一个程序来帮助你选择一个轻松的踩踏方式,使得能量小号最少。

为了简单起见,将一个八分音符作为一个基本时间单位,每个时间单位要么需要踩一个箭头(不会同时需要踩两个箭头),要么什么都不需要踩。在任意时刻,你的左右脚应放在不同的两个箭头上,且每个时间单位内只有一只脚能动(移动和/或踩箭头),不能跳跃。另外,你必须面朝前方以看到屏幕(即:你不能把左脚放在右箭头上,并且右脚放在左箭头上)。当你执行一个动作(移动和/或踩)时,消耗的能量这样计算

(紫书上的说明是错的= =)

Performing an action with a foot costs 1 unit of energy if it did NOT perform an action in the previous time unit. If it did, then it costs 3 units if it doesn't change arrows, 5 units if it moves to an adjacent arrow, and 7 units if it moves directly across the pad (between Up and Down, or Left and Right).

正常情况下,你的左脚不能放到右箭头上(或者反之),但有一种情况例外:如果你的左脚在上箭头或者下箭头,你可以临时扭着身子用右脚踩左箭头,但是在你的右脚移出左箭头之前,你的左脚都不能移到另一个箭头上。类似地,右脚在上箭头或者下箭头时,你也可以临时用左脚踩右箭头。一开始,你的左脚在左箭头上,右脚在右箭头上。

输入包含最多100组数据,每组数据包含一个长度不超过70的字符串,即各个时间单位需要踩的箭头。L和R分别表示左右箭头,“.”表示不需要踩箭头。输出应是一个长度和输入相同的字符串,表示每个时间单位执行动作的脚。L和R分别是左右脚,“.”表示不踩。比如, .RDLU 的最优解是 RLRLR ,第一次是把右脚放在下箭头上。

题解

因为最多只有70个阶段,所以不会爆栈,直接递归,懒得改迭代了= =

设$dp[l][r][t][id]$为时间为$t$,左脚在$l$,右脚在$r$,且上一次移动了(id==1?左:右)脚

很容易写出转移= =

状态和转移最多$\mathcal{O}(lrt\times id) \leqslant 2240$,完全不管时间限制……

紫书上给的能量消耗说明是错的,害得我改了好久= =

AC代码

#include<bits/stdc++.h>
using namespace std; #define REP(r,x,y) for(register int r=(x); r<(y); r++)
#define PER(r,x,y) for(register int r=(x); r>(y); r--)
#define REPE(r,x,y) for(register int r=(x); r<=(y); r++)
#define PERE(r,x,y) for(register int r=(x); r>=(y); r--)
#ifdef sahdsg
#define DBG(...) printf(__VA_ARGS__)
#else
#define DBG(...) (void)0
#endif
#define iabs(a) ((a)<0?(-(a)):(a))
char ops[80];
int d[4][4][80][3];
inline int getnum(int x) {
switch(ops[x]) {
case 'U': return 0;
case 'L': return 1;
case 'D': return 2;
case 'R': return 3;
case '.': return -1;
}
return -1;
} inline bool can(int l, int r, int ll, int lr) {
if(l==r) return false;
if((ll==2 || ll==0) && lr==1 && l!=ll) return false;
if((lr==2 || lr==0) && ll==3 && r!=lr) return false;
if(l==3 && r==1) return false;
return true;
} inline int cost(int f, int t) {
if(f==t) return 3;
if(iabs(f-t)==2) return 7;
return 5;
} int solve(int l, int r, int t, int id) {
if(ops[t]<=' ') return 0;
int &now = d[l][r][t][id];
if(now>=0) return now;
int num=getnum(t); now=0x3f3f3f3f;
if(num>=0) {
if(can(l,num,l,r)) now=min(now,solve(l,num,t+1, 2)+(id==2?cost(r,num):1));
if(can(num,r,l,r)) now=min(now,solve(num,r,t+1, 1)+(id==1?cost(l,num):1));
} else {
REP(i,0,4) {
if(can(l,i,l,r)) now=min(now,solve(l,i,t+1, 2)+(id==2?cost(r,i):1));
if(can(i,r,l,r)) now=min(now,solve(i,r,t+1, 1)+(id==1?cost(l,i):1));
}
now=min(now,solve(l,r,t+1,0));
}
return now;
}
char ans[80];
int ansn=0;
inline void anx(char x) {
ans[ansn++]=x;
}
bool prn(int l, int r, int t, int id) {
if(ops[t]<=' ') return true;
int &now = d[l][r][t][id];
int num=getnum(t);
if(num>=0) {
if(can(l,num,l,r)) if(now==solve(l,num,t+1, 2)+(id==2?cost(r,num):1))
if(prn(l,num,t+1, 2)) {anx('R'); return 1;}
if(can(num,r,l,r)) if(now==solve(num,r,t+1, 1)+(id==1?cost(l,num):1))
if(prn(num,r,t+1, 1)) {anx('L'); return 1;}
} else {
REP(i,0,4) {
if(can(l,i,l,r)) if(now==solve(l,i,t+1, 2)+(id==2?cost(r,i):1))
if(prn(l,i,t+1,2)) {anx('R'); return 1;}
if(can(i,r,l,r)) if(now==solve(i,r,t+1, 1)+(id==1?cost(l,i):1))
if(prn(i,r,t+1,1)) {anx('L'); return 1;}
}
if(now==solve(l,r,t+1,0)) if(prn(l,r,t+1,0)) {anx('.'); return 1;}
}
return now;
} int main() {
#ifdef sahdsg
freopen("in.txt","r",stdin);
#endif
while(1) {
fgets(ops, 80, stdin); if(ops[0]=='#') break;
memset(d,-1,sizeof d); ansn=0;
solve(1,3,0,0); //DBG("%d\n", d[1][3][0][0]);
prn(1,3,0,0);
while(0<ansn--) putchar(ans[ansn]); putchar('\n');
}
return 0;
}
上一篇:Angular.element和$document的使用方法分析,代替jquery


下一篇:C++ 矩阵库 eigen