JOI 12 本選 Gifts ( DP )
Gifts | Aizu Online Judge
kagamiz.hatenablog.com
kagamizさんの記事見て分かりました、ありがとうございます。
重要な考察は、最大3歩しか戻れないという事は、6歩前までの状態としか関係ないという事だ。なので今までの最後の6歩の方向を記録します。方向をバイナリでエンコードすると( 1 << ( 2 * 6 ) )でできます。すると転移の際、そのレコードをちょっと見ればどのマスがまだ取られていないかがわかるようになる。
つまらないバグで午後丸ごと台無しにした。その方向のレコードに mod掛けるの忘れた。
#include <bits/stdc++.h> using namespace std; const int MAXH = 50 + 5; const int MAXW = 50 + 5; const int MAXK = 3 + 1; const int INF = 0x3f3f3f3f; const int dx[] = { 0, 1, 0, -1 }; const int dy[] = { 1, 0, -1, 0 }; void upmax(int &x, int v){ if( x < v ) x = v; } int h, w, k; char G[ MAXH ][ MAXW ]; int dp[ MAXH ][ MAXW ][ MAXK ][ 1 << 12 ]; bool outOfRange(int x, int y){ return x < 0 || x >= h || y < 0 || y >= w; } bool revisit(int seq){ int tx = 0, ty = 0; for(int i = 0; i < 6; ++i, seq >>= 2){ tx += dx[ seq % 4 ]; ty += dy[ seq % 4 ]; if( tx == 0 && ty == 0 ) return true; } return false; } void solve(){ memset( dp, -1, sizeof(dp) ); dp[ 0 ][ 0 ][ 0 ][ 0 ] = G[ 0 ][ 0 ] - '0'; for(int g = 0; g <= k; ++g) for(int i = 0; i < h; ++i) for(int j = 0; j < w; ++j) for(int s = 0; s < ( 1 << 12 ); ++s){ if( dp[ i ][ j ][ g ][ s ] < 0 ) continue; for(int di = 0; di < 4; ++di){ int ni = i + dx[ di ]; int nj = j + dy[ di ]; int ng = g + ( di >= 2 ); int ns = ( ( s << 2 ) + di ) % ( 1 << 12 ); if( outOfRange( ni, nj ) ) continue; if( G[ ni ][ nj ] == '#' ) continue; if( ng > k ) continue; int val = 0; if( !revisit( ns ) ) val = G[ ni ][ nj ] - '0'; upmax( dp[ ni ][ nj ][ ng ][ ns ], dp[ i ][ j ][ g ][ s ] + val ); // printf("dp[ %d ][ %d ][ %d ][ %d ] <- dp[ %d ][ %d ][ %d ][ %d ] + %d = %d\n", ni, nj, ng, ns, i, j, g, s, val, dp[ ni ][ nj ][ ng ][ ns ]); } } int ans = 0; for(int g = 0; g <= k; ++g) for(int s = 0; s < ( 1 << 12 ); ++s) upmax( ans, dp[ h - 1 ][ w - 1 ][ g ][ s ] ); printf("%d\n", ans); } int main(){ scanf("%d%d%d", &h, &w, &k); for(int i = 0; i < h; ++i){ scanf("%s", &G[ i ]); for(int j = 0; j < w; ++j) if( G[ i ][ j ] == '.' ) G[ i ][ j ] = '0'; } solve(); return 0; }