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"}

*/