SRM 659 Div1 CampLunch

contents

1. 1. Problem
2. 2. Solution

Problem

有 M 個人連續 N 天都在同一個地方吃飯，請問它們購買餐點方案數。

• 與當天坐在相鄰附近的人，一起購買雙人分享餐，解決這天。
• 買一份雙人分享餐，連續吃兩天。
• 買一份單人餐，解決這天。

Solution

淡淡地憂傷，一個人買雙人分享餐吃兩天 … 不過沒關係，一道插頭 dp，相當於插入 $1 \times 2$ 或 $2 \times 1$ 塞滿盤面。但每一天相鄰的人都不同，因此壓縮 bitmask 狀態會需要變動，統一紀錄 $[1<<M]$ ，表示 $i-bit$ 第 $i$ 個人是否已經解決今天，接著對應 (up = self, left = 查找位置)，滾動數組進行轉移。

可以參照 UVa 11270 的解法。現在要處理的是變化的 colume 填充。

#include <stdio.h>
#include <vector>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;

const long long MOD = 1000000007;
const int MAXN = 17, MAXM = 17;
class CampLunch {
public:
	int dp[2][1<<MAXM];
	int count(int N, int M, vector <string> a) {
		memset(dp, 0, sizeof(dp));
		int flag = 0;
		dp[0][(1<<M)-1] = 1;
		for (int i = 0; i < N; i++) {			
			for (int j = 0; j < M; j++) {
				int p = flag, q = !flag;
				flag = 1 - flag;
				memset(dp[q], 0, sizeof(dp[q]));
				for (int k = (1<<M)-1; k >= 0; k--) {
					int L, U;
					int Lid, Uid;
					int ways = dp[p][k];
					
					if (ways == 0)
						continue;
					
					Lid = j == 0 ? -1 : (a[i][j-1] - 'A');
					Uid = a[i][j] - 'A';
					L = j == 0 ? 1 : ((k>>(Lid))&1);
					U = (k>>Uid)&1;
										
					if (L == 0 && U == 1) 	// plan 1, sit next to each other
						dp[q][k|(1<<Lid)] = (dp[q][k|(1<<Lid)] + ways)%MOD;
					if (U == 0) 			// plan 2, two consecutive days.
						dp[q][k|(1<<Uid)] = (dp[q][k|(1<<Uid)] + ways)%MOD;
					if (U == 1)				// plan 3, single
						dp[q][k|(1<<Uid)] = (dp[q][k|(1<<Uid)] + ways)%MOD;
					if (U == 1)				// reserve
						dp[q][k^(1<<Uid)] = (dp[q][k^(1<<Uid)] + ways)%MOD;
				}
			}
		}
		
		return dp[flag][(1<<M)-1];
	}
};

int main() {
	CampLunch cl;
	string v[] = {"ABC","ABC"};
	int vv = cl.count(2, 3, vector<string>(v, v+2));
	printf("%d\n", vv);
	return 0;
}
/*
 2
2
{"AB","AB"}

*/