Artifact 55b5f1c30cb956ae0ebe0bd6bcc403c0570002f3:
0000: 23 69 6e 63 6c 75 64 65 20 3c 76 65 63 74 6f 72 #include <vector
0010: 3e 0a 75 73 69 6e 67 20 6e 61 6d 65 73 70 61 63 >.using namespac
0020: 65 20 73 74 64 3b 0a 0a 73 74 72 75 63 74 20 48 e std;..struct H
0030: 69 6c 6c 48 69 6b 65 0a 7b 0a 09 6c 6f 6e 67 20 illHike.{..long
0040: 6c 6f 6e 67 20 6e 75 6d 50 61 74 68 73 28 69 6e long numPaths(in
0050: 74 20 64 69 73 74 61 6e 63 65 2c 20 69 6e 74 20 t distance, int
0060: 6d 61 78 48 65 69 67 68 74 2c 20 76 65 63 74 6f maxHeight, vecto
0070: 72 3c 69 6e 74 3e 20 6c 61 6e 64 6d 61 72 6b 73 r<int> landmarks
0080: 29 0a 09 7b 0a 09 09 2f 2f 20 72 65 61 63 68 65 )..{...// reache
0090: 64 2d 6d 61 78 48 65 69 67 68 74 3f 2c 20 23 72 d-maxHeight?, #r
00a0: 65 61 63 68 65 64 2d 6c 61 6e 64 6d 61 72 6b 73 eached-landmarks
00b0: 2c 20 63 75 72 72 65 6e 74 2d 68 65 69 67 68 74 , current-height
00c0: 0a 09 09 6c 6f 6e 67 20 6c 6f 6e 67 20 62 75 66 ...long long buf
00d0: 31 5b 32 5d 5b 35 31 5d 5b 35 31 5d 3d 7b 30 7d 1[2][51][51]={0}
00e0: 2c 20 62 75 66 32 5b 32 5d 5b 35 31 5d 5b 35 31 , buf2[2][51][51
00f0: 5d 2c 20 28 2a 64 70 29 5b 35 31 5d 5b 35 31 5d ], (*dp)[51][51]
0100: 3d 62 75 66 31 3b 0a 09 09 64 70 5b 30 5d 5b 30 =buf1;...dp[0][0
0110: 5d 5b 30 5d 20 3d 20 31 3b 0a 0a 09 09 66 6f 72 ][0] = 1;....for
0120: 28 69 6e 74 20 64 3d 31 3b 20 64 3c 3d 64 69 73 (int d=1; d<=dis
0130: 74 61 6e 63 65 3b 20 2b 2b 64 29 0a 09 09 7b 0a tance; ++d)...{.
0140: 09 09 09 6c 6f 6e 67 20 6c 6f 6e 67 20 28 2a 64 ...long long (*d
0150: 70 32 29 5b 35 31 5d 5b 35 31 5d 20 3d 20 28 64 p2)[51][51] = (d
0160: 70 3d 3d 62 75 66 31 20 3f 20 62 75 66 32 20 3a p==buf1 ? buf2 :
0170: 20 62 75 66 31 29 3b 0a 09 09 09 6d 65 6d 73 65 buf1);....memse
0180: 74 28 64 70 32 2c 20 30 2c 20 73 69 7a 65 6f 66 t(dp2, 0, sizeof
0190: 28 6c 6f 6e 67 20 6c 6f 6e 67 29 2a 32 2a 35 31 (long long)*2*51
01a0: 2a 35 31 29 3b 0a 0a 09 09 09 66 6f 72 28 69 6e *51);.....for(in
01b0: 74 20 72 6d 3d 30 3b 20 72 6d 3c 3d 31 3b 20 2b t rm=0; rm<=1; +
01c0: 2b 72 6d 29 0a 09 09 09 09 66 6f 72 28 69 6e 74 +rm).....for(int
01d0: 20 72 6c 3d 30 3b 20 72 6c 3c 3d 6c 61 6e 64 6d rl=0; rl<=landm
01e0: 61 72 6b 73 2e 73 69 7a 65 28 29 3b 20 2b 2b 72 arks.size(); ++r
01f0: 6c 29 0a 09 09 09 09 09 66 6f 72 28 69 6e 74 20 l)......for(int
0200: 63 68 3d 30 3b 20 63 68 3c 3d 6d 61 78 48 65 69 ch=0; ch<=maxHei
0210: 67 68 74 3b 20 2b 2b 63 68 29 0a 09 09 09 09 09 ght; ++ch)......
0220: 7b 0a 09 09 09 09 09 09 69 66 28 63 68 3e 31 20 {.......if(ch>1
0230: 7c 7c 20 64 3d 3d 64 69 73 74 61 6e 63 65 20 26 || d==distance &
0240: 26 20 63 68 3e 30 29 0a 09 09 09 09 09 09 7b 0a & ch>0).......{.
0250: 09 09 09 09 09 09 09 64 70 32 5b 72 6d 5d 0a 09 .......dp2[rm]..
0260: 09 09 09 09 09 09 20 20 20 5b 72 6c 3c 6c 61 6e ...... [rl<lan
0270: 64 6d 61 72 6b 73 2e 73 69 7a 65 28 29 20 26 26 dmarks.size() &&
0280: 20 6c 61 6e 64 6d 61 72 6b 73 5b 72 6c 5d 3d 3d landmarks[rl]==
0290: 63 68 2d 31 20 3f 20 72 6c 2b 31 20 3a 20 72 6c ch-1 ? rl+1 : rl
02a0: 5d 0a 09 09 09 09 09 09 09 20 20 20 5b 63 68 2d ]........ [ch-
02b0: 31 5d 20 2b 3d 20 64 70 5b 72 6d 5d 5b 72 6c 5d 1] += dp[rm][rl]
02c0: 5b 63 68 5d 3b 0a 09 09 09 09 09 09 7d 0a 09 09 [ch];.......}...
02d0: 09 09 09 09 69 66 28 63 68 3e 30 20 7c 7c 20 64 ....if(ch>0 || d
02e0: 3d 3d 64 69 73 74 61 6e 63 65 29 0a 09 09 09 09 ==distance).....
02f0: 09 09 7b 0a 09 09 09 09 09 09 09 64 70 32 5b 72 ..{........dp2[r
0300: 6d 5d 0a 09 09 09 09 09 09 09 20 20 20 5b 72 6c m]........ [rl
0310: 3c 6c 61 6e 64 6d 61 72 6b 73 2e 73 69 7a 65 28 <landmarks.size(
0320: 29 20 26 26 20 6c 61 6e 64 6d 61 72 6b 73 5b 72 ) && landmarks[r
0330: 6c 5d 3d 3d 63 68 20 3f 20 72 6c 2b 31 20 3a 20 l]==ch ? rl+1 :
0340: 72 6c 5d 0a 09 09 09 09 09 09 09 20 20 20 5b 63 rl]........ [c
0350: 68 5d 20 2b 3d 20 64 70 5b 72 6d 5d 5b 72 6c 5d h] += dp[rm][rl]
0360: 5b 63 68 5d 3b 0a 09 09 09 09 09 09 7d 0a 09 09 [ch];.......}...
0370: 09 09 09 09 69 66 28 20 63 68 3c 6d 61 78 48 65 ....if( ch<maxHe
0380: 69 67 68 74 20 29 0a 09 09 09 09 09 09 7b 0a 09 ight ).......{..
0390: 09 09 09 09 09 09 64 70 32 5b 63 68 2b 31 3d 3d ......dp2[ch+1==
03a0: 6d 61 78 48 65 69 67 68 74 20 3f 20 31 20 3a 20 maxHeight ? 1 :
03b0: 72 6d 5d 0a 09 09 09 09 09 09 09 20 20 20 5b 72 rm]........ [r
03c0: 6c 3c 6c 61 6e 64 6d 61 72 6b 73 2e 73 69 7a 65 l<landmarks.size
03d0: 28 29 20 26 26 20 6c 61 6e 64 6d 61 72 6b 73 5b () && landmarks[
03e0: 72 6c 5d 3d 3d 63 68 2b 31 20 3f 20 72 6c 2b 31 rl]==ch+1 ? rl+1
03f0: 20 3a 20 72 6c 5d 0a 09 09 09 09 09 09 09 20 20 : rl]........
0400: 20 5b 63 68 2b 31 5d 20 2b 3d 20 64 70 5b 72 6d [ch+1] += dp[rm
0410: 5d 5b 72 6c 5d 5b 63 68 5d 3b 0a 09 09 09 09 09 ][rl][ch];......
0420: 09 7d 0a 09 09 09 09 09 7d 0a 0a 09 09 09 64 70 .}......}.....dp
0430: 20 3d 20 64 70 32 3b 0a 09 09 7d 0a 0a 09 09 72 = dp2;...}....r
0440: 65 74 75 72 6e 20 64 70 5b 31 5d 5b 6c 61 6e 64 eturn dp[1][land
0450: 6d 61 72 6b 73 2e 73 69 7a 65 28 29 5d 5b 30 5d marks.size()][0]
0460: 3b 0a 09 7d 0a 7d 3b 0a ;..}.};.