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; }
转载于:https://www.cnblogs.com/sahdsg/p/10596948.html
相关资源：JAVA上百实例源码以及开源项目