Artifact 55b5f1c30cb956ae0ebe0bd6bcc403c0570002f3

• File SRM/145/1C.cpp
  • 2011-02-23 09:21:16 - part of checkin [4fd800b3a8] on branch trunk - Copied from private svn repository. (user: kinaba) [annotate]

#include <vector>
using namespace std;

struct HillHike
{
	long long numPaths(int distance, int maxHeight, vector<int> landmarks)
	{
		// reached-maxHeight?, #reached-landmarks, current-height
		long long buf1[2][51][51]={0}, buf2[2][51][51], (*dp)[51][51]=buf1;
		dp[0][0][0] = 1;

		for(int d=1; d<=distance; ++d)
		{
			long long (*dp2)[51][51] = (dp==buf1 ? buf2 : buf1);
			memset(dp2, 0, sizeof(long long)*2*51*51);

			for(int rm=0; rm<=1; ++rm)
				for(int rl=0; rl<=landmarks.size(); ++rl)
					for(int ch=0; ch<=maxHeight; ++ch)
					{
						if(ch>1 || d==distance && ch>0)
						{
							dp2[rm]
							   [rl<landmarks.size() && landmarks[rl]==ch-1 ? rl+1 : rl]
							   [ch-1] += dp[rm][rl][ch];
						}
						if(ch>0 || d==distance)
						{
							dp2[rm]
							   [rl<landmarks.size() && landmarks[rl]==ch ? rl+1 : rl]
							   [ch] += dp[rm][rl][ch];
						}
						if( ch<maxHeight )
						{
							dp2[ch+1==maxHeight ? 1 : rm]
							   [rl<landmarks.size() && landmarks[rl]==ch+1 ? rl+1 : rl]
							   [ch+1] += dp[rm][rl][ch];
						}
					}

			dp = dp2;
		}

		return dp[1][landmarks.size()][0];
	}
};