SRM 605 D1 L2：AlienAndSetDiv1，DP，bitmask

編輯：關於Android編程

跟D2 L3 類似，唯一的區別是D2L3是兩數之差至多為K, 這題是至少K，增加了一點難度，DP的狀態不好想。類似D2L3，只考慮未匹配的數，不過將未匹配的數分成了兩類，一類是Good integers，g >= n + K，另一類是, s > n && s < n + K。以從大到小的順序考慮2N個數。

代碼如下：

#include 
#include 
#include 

#include 
#include 
#include 
#include 
#include 
#include 
#include

#include 
#include 
#include 
#include 
#include 

using namespace std;


/*************** Program Begin **********************/
const int MOD = 1000000007;  
const int MAX_N = 50;
const int MAX_K = 10;
int dp[2 * MAX_N + 1][2 * MAX_N + 1][1 << MAX_K];

class AlienAndSetDiv1 {
public:
	int K;
	int calc(int s, int g, int n)
	{
		int res = 0;
		if (-1 != dp[n][g][s]) {
			return dp[n][g][s];
		}
		if (n == 0) {
			if (0 == s && 0 == g) {		// base case
				res = 1;
			}
		} else {
			if (0 == s && 0 == g) {
				if (1 == K) {
					res += 2 * calc(0, 1, n-1);	// add
				} else {
					res += 2 * calc(1, 0, n-1);	// add
				}
				res %= MOD;
			} else if (0 == s && g != 0) {
				res += calc(0, g-1, n-1);	// match
				if (1 == K) {
					res += calc(0, g+1, n-1);	// add
				} else {
					res += calc(1, g, n-1);	// add
				}
				res %= MOD;
			} else if (s != 0 && 0 == g) {		// K != 1，只能add
				int newset = s;
				int i = 0;  
				for (i = 0; (newset & 0x80000000 ) == 0; newset = ( newset << 1 ), ++i) {  
					// 注意位操作的優先級，要加括號
				}  
				int mx = 31 - i;    // mx 為s不為0的最高位
				if (n + mx + 1 - (n - 1) >= K) {	// g -> 1
					int t = (s - (1 << mx));	// 清除mx位
					res += calc( (t << 1) | 1, 1, n - 1 );	// add
					res %= MOD;
				} else {
					res += calc( (s << 1) | 1, 0, n - 1 );	// add
					res %= MOD;
				}
			} else {	// s != 0 && 0 != g	// K != 1
				int newset = s;
				int i = 0;  
				for (i = 0; (newset & 0x80000000 ) == 0; newset = ( newset << 1 ), ++i) {
				}  
				int mx = 31 - i;    // mx 為s不為0的最高位

				if ( n + mx + 1 - (n - 1) >= K) {	// 判斷是否使g變化
					int t = (s - (1 << mx));
					res += calc(t << 1, g, n-1);	// match
					res += calc( (t << 1) | 1, g+1, n - 1 ); // add
				} else {
					res += calc(s << 1, g-1, n-1);	// match
					res += calc( (s << 1) | 1, g, n - 1 );	// add
				}
				res %= MOD;
			}
		}

		dp[n][g][s] = res;
		return res;
	}

	int getNumber(int N, int K) {
		int res = 0;
		this->K = K;
		memset(dp, -1, sizeof(dp));
		res = calc(0, 0, 2 * N);
		return res;
	}
};

/************** Program End ************************/

上一頁:Android JNI之Android.mk、Application.mk
下一頁:Android聯系人中添加歸屬地分組

關於Android編程