首页 > 代码库 > UVA 10564 Paths through the Hourglass
UVA 10564 Paths through the Hourglass
题解:
dp[i][j][k]表示在第i行第j列数时还有k值的方法数
k初始为s
不难构造转移方程,注意边界条件
这次还要输出字典序最小的路径。
所以在dp时,需要从下往上更新,然后在第一行选择最左边的
used[i][j][k][m] 表示在第i行第j列数时还有k值可以向左还是向右,左为0,右为1,优先左
代码:
#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 ll INF = 1e18; const int maxn = 550; const int M = 4000; int n, s, m; int a[ 50 ][ 50 ], used[ 50 ][ 50 ][ 505 ][ 2 ]; ll dp[ 50 ][ 50 ][ 505 ]; int main() { while( ~scanf( "%d%d", &n, &s ) && n ) { for( int i = 1; i <= 2 * n - 1; i ++ ) { if( i <= n ) m = n + 1 - i; else m = i + 1 - n; for( int j = 1; j <= m; j ++ ) scanf( "%d", &a[ i ][ j ] ); } memset( dp, 0, sizeof( dp ) ); memset( used,0,sizeof( used ) ); for( int i = 1; i <= n; i ++ ) dp[ 2 * n - 1 ][ i ][ s - a[ 2 * n - 1 ][ i ] ] = 1; for( int i = 2 * n - 2; i >= 1; i -- ) { if( i >= n ) { m = i + 1 - n; for( int j = 1; j <= m; j ++ ) { for( int k = a[ i ][ j ]; k <= s; k ++ ) { dp[ i ][ j ][ k - a[ i ][ j ] ] += dp[ i + 1 ][ j ][ k ]; if( dp[ i + 1 ][ j ][ k ] > 0 ) used[ i ][ j ][ k - a[ i ][ j ] ][ 0 ] = 1; dp[ i ][ j ][ k - a[ i ][ j ] ] += dp[ i + 1 ][ j + 1 ][ k ]; if( dp[ i + 1 ][ j + 1 ][ k ] > 0 ) used[ i ][ j ][ k - a[ i ][ j ] ][ 1 ] = 1; } } } else { m = n + 1 - i; for( int j = 1; j <= m; j ++ ) { for( int k = a[ i ][ j ]; k <= s; k ++ ) { if( j - 1 > 0 ) { dp[ i ][ j ][ k - a[ i ][ j ] ] += dp[ i + 1 ][ j - 1 ][ k ]; if( dp[ i + 1 ][ j - 1 ][ k ] > 0 ) used[ i ][ j ][ k - a[ i ][ j ] ][ 0 ] = 1; } if( j < m ) { dp[ i ][ j ][ k - a[ i ][ j ] ] += dp[ i + 1 ][ j ][ k ]; if( dp[ i + 1 ][ j ][ k ] > 0 ) used[ i ][ j ][ k - a[ i ][ j ] ][ 1 ] = 1; } } } } } ll cnt = 0; int pos = -1, num = 0; for( int i = 1; i <= n; i ++ ) { cnt += dp[ 1 ][ i ][ 0 ]; if( pos == -1 && dp[ 1 ][ i ][ 0 ] > 0 ) pos = i; } printf( "%lld\n", cnt ); if( cnt == 0 ) printf( "\n" ); else { printf( "%d ", pos - 1 ); int p = 1; while( p < 2 * n - 1 ) { int tmp = a[ p ][ pos ]; if( used[ p ][ pos ][ num ][ 0 ] ) { printf( "L" ); if( p < n ) pos --; } else { printf( "R" ); if( p >= n ) pos ++; } num += tmp; p ++; } printf( "\n" ); } } return 0; }
UVA 10564 Paths through the Hourglass
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。