首页 > 代码库 > UVALive 2031 Dance Dance Revolution
UVALive 2031 Dance Dance Revolution
题解:
简单DP
dp[i][j][k] 表示第i步双脚在位置j和位置k的位置
然后根据题意推一下转移方程就行了
代码:
#include<bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define se second #define fs first #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define pii pair<int,int> #define ll long long const int INF = 1e9; const int maxn = 50050; vector< int > v; int x; int dp[ maxn ][ 5 ][ 5 ]; int step_num( int s, int e ) { if( s == 0 ) return 2; if( s == 1 ) { if( e == 1 ) return 1; if( e == 2 || e == 4 ) return 3; if( e == 3 ) return 4; } if( s == 2 ) { if( e == 2 ) return 1; if( e == 1 || e == 3 ) return 3; if( e == 4 ) return 4; } if( s == 3 ) { if( e == 3 ) return 1; if( e == 2 || e == 4 ) return 3; if( e == 1 ) return 4; } if( s == 4 ) { if( e == 4 ) return 1; if( e == 1 || e == 3 ) return 3; if( e == 2 ) return 4; } } int main() { while( ~scanf( "%d", &x ) && x ) { v.clear(); v.push_back( x ); while( scanf( "%d", &x ) && x ) v.push_back( x ); for( int i = 0; i < 5; i ++ ) for( int j = 0; j < 5; j ++ ) for( int k = 0; k < 50000; k ++ ) dp[ k ][ i ][ j ] = INF; int n = v.size(), goal = INF; dp[ 1 ][ 0 ][ v[ 0 ] ] = dp[ 1 ][ v[ 0 ] ][ 0 ] = 2; for( int i = 2; i <= n; i ++ ) { int now = v[ i - 1 ]; for( int j = 0; j < 5; j ++ ) for( int k = 0; k < 5; k ++ ) { if( j == k ) continue; if( j != now ) dp[ i ][ j ][ now ] = min( dp[ i ][ j ][ now ], dp[ i - 1 ][ j ][ k ] + step_num( k, now ) ); if( k != now ) dp[ i ][ now ][ k ] = min( dp[ i ][ now ][ k ], dp[ i - 1 ][ j ][ k ] + step_num( j, now ) ); if( i == n ) { goal = min( goal, dp[ i ][ now ][ k ] ); goal = min( goal, dp[ i ][ j ][ now ] ); } } } printf( "%d\n", goal ); } return 0; }
UVALive 2031 Dance Dance Revolution
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。