4fd800b3a8 2011-02-23        kinaba: #include <vector>
4fd800b3a8 2011-02-23        kinaba: using namespace std;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: struct HillHike
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: 	long long numPaths(int distance, int maxHeight, vector<int> landmarks)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		// reached-maxHeight?, #reached-landmarks, current-height
4fd800b3a8 2011-02-23        kinaba: 		long long buf1[2][51][51]={0}, buf2[2][51][51], (*dp)[51][51]=buf1;
4fd800b3a8 2011-02-23        kinaba: 		dp[0][0][0] = 1;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		for(int d=1; d<=distance; ++d)
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			long long (*dp2)[51][51] = (dp==buf1 ? buf2 : buf1);
4fd800b3a8 2011-02-23        kinaba: 			memset(dp2, 0, sizeof(long long)*2*51*51);
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 			for(int rm=0; rm<=1; ++rm)
4fd800b3a8 2011-02-23        kinaba: 				for(int rl=0; rl<=landmarks.size(); ++rl)
4fd800b3a8 2011-02-23        kinaba: 					for(int ch=0; ch<=maxHeight; ++ch)
4fd800b3a8 2011-02-23        kinaba: 					{
4fd800b3a8 2011-02-23        kinaba: 						if(ch>1 || d==distance && ch>0)
4fd800b3a8 2011-02-23        kinaba: 						{
4fd800b3a8 2011-02-23        kinaba: 							dp2[rm]
4fd800b3a8 2011-02-23        kinaba: 							   [rl<landmarks.size() && landmarks[rl]==ch-1 ? rl+1 : rl]
4fd800b3a8 2011-02-23        kinaba: 							   [ch-1] += dp[rm][rl][ch];
4fd800b3a8 2011-02-23        kinaba: 						}
4fd800b3a8 2011-02-23        kinaba: 						if(ch>0 || d==distance)
4fd800b3a8 2011-02-23        kinaba: 						{
4fd800b3a8 2011-02-23        kinaba: 							dp2[rm]
4fd800b3a8 2011-02-23        kinaba: 							   [rl<landmarks.size() && landmarks[rl]==ch ? rl+1 : rl]
4fd800b3a8 2011-02-23        kinaba: 							   [ch] += dp[rm][rl][ch];
4fd800b3a8 2011-02-23        kinaba: 						}
4fd800b3a8 2011-02-23        kinaba: 						if( ch<maxHeight )
4fd800b3a8 2011-02-23        kinaba: 						{
4fd800b3a8 2011-02-23        kinaba: 							dp2[ch+1==maxHeight ? 1 : rm]
4fd800b3a8 2011-02-23        kinaba: 							   [rl<landmarks.size() && landmarks[rl]==ch+1 ? rl+1 : rl]
4fd800b3a8 2011-02-23        kinaba: 							   [ch+1] += dp[rm][rl][ch];
4fd800b3a8 2011-02-23        kinaba: 						}
4fd800b3a8 2011-02-23        kinaba: 					}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 			dp = dp2;
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		return dp[1][landmarks.size()][0];
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: };