UVA10618 跳舞机 Tango Tango Insurrection

towboa / 2023-04-28 / 原文

有四个踩踏板，不同的踩踏方式消耗不同的力气

问最小花费的力气

F[ i ] [ a] [b ][ s] ， s 是上一次哪只角移动了( 0 ,1,2 )

https://www.luogu.com.cn/problem/UVA10618

#include<iostream>
#include <cstring>
#include <algorithm>
const int N =1003;
#define inf 1e9
#define UP 0
#define LEFT 1
#define RIGHT 2
#define DOWN 3

char str[N] ,opt[]=".LR";
int n,f[N][5][5][3], op[N][4][4][3];


int get(int a,int b){
	if(a == b) return 3;
	if(a+b == 3) return 7;
	return 5;
}
int energy(int i,int a,int b,int s,int g,int t,int &ta,int &tb){
	ta=a,tb=b;
	if(g == 1) ta=t;
	else if(g == 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 res;
	if(g == 0) res=0;
	else if(g != s) res=1;
	else{
		if(g == 1) res=get(a,ta);
		else res=get(b,tb);
	}
	return res;
}

void mov(int i,int a,int b,int s,int g,int t){
	int ta,tb;
	int E=energy(i,a,b,s,g,t,ta,tb);
	if(E < 0) return;
	int cost=f[i+1][ta][tb][g]+E;
	int &v=f[i][a][b][s];
	if(cost < v){
		v=cost;
		op[i][a][b][s]=g*4+t;
	}
}
void sov(){
	int i ,a,b; 
	for(i=n-1;i>=0;i--)
	 for(a=0;a<4;a++)
	  for(b=0;b<4;b++)
	  	 if(a!=b) {
	  	 	
			for(int s=0;s<3;s++){
				 f[i][a][b][s] = inf ;
			if(str[i]=='.'){
				mov(i,a,b,s,0,0) ;
				for(int t=0;t<4;t++){
					mov(i,a,b,s,1,t);
					mov(i,a,b,s,2,t);
				}
			}
			else{
				if(str[i]=='U'){
					mov(i,a,b,s,1,0);
					mov(i,a,b,s,2,0);
				}
				else if(str[i]=='L'){
					mov(i,a,b,s,1,1) ;
					mov(i,a,b,s,2,1);
				}
				else if(str[i]=='R'){
					mov(i,a,b,s,1,2);
					mov(i,a,b,s,2,2);
				}
				else{
					mov(i,a,b,s,1,3) ;
					mov(i,a,b,s,2,3) ;
				}
			}
		  }
		 }
}
signed main () {
	while(std::cin>>str){
		if(str[0] == '#') break;
		n=strlen(str);
		memset(f,0,sizeof f);

		sov();

		int a=LEFT,b=RIGHT,s=0;
		for(int i=0;i<n;++i){
			int g=op[i][a][b][s]/4;
			int t=op[i][a][b][s]%4;
			printf("%c",opt[g]);
			s=g;
			if(g == 1) a=t;
			else if(g == 2) b=t;
		}
		puts("");
	}
}