백준[1657] 두부장수 장홍준

문제 설명

문제 링크

http://icpc.me/1657

풀이

비트 마스크를 하면서 dp를 돌면 된다.

백준[1648] 격자판 채우기와 거의 유사한 문제이다.

위의 문제와 차이점은 현재 칸을 안 채우고 넘어가는 경우가 있는 것이다.

코드

#include <bits/stdc++.h>
using namespace std;

int dp[15 * 15][1 << 14], n, m;
string value;

int calValue(string s) {
    if (s[0] > s[1]) swap(s[0], s[1]);
    if (s[0] == 'A') {
        if (s[1] == 'A') return 10;
        if (s[1] == 'B') return 8;
        if (s[1] == 'C') return 7;
        if (s[1] == 'D') return 5;
        if (s[1] == 'F') return 1;
    } else if (s[0] == 'B') {
        if (s[1] == 'B') return 6;
        if (s[1] == 'C') return 4;
        if (s[1] == 'D') return 3;
        if (s[1] == 'F') return 1;
    } else if (s[0] == 'C') {
        if (s[1] == 'C') return 3;
        if (s[1] == 'D') return 2;
        if (s[1] == 'F') return 1;
    } else if (s[0] == 'D') {
        if (s[1] == 'D') return 2;
        if (s[1] == 'F') return 1;
    } else return 0;
    return 0;
}

int dpf(int k, int s) {
    int &ret = dp[k][s];
    if (~ret) return ret;
    if (k == n * m && !s) return 0;
    if (k >= n * m && s) return -1e9;
    
    ret = 0;
    ret = max(ret, dpf(k + 1, s >> 1));
    if (s & 1) {
        ret = max(ret, dpf(k + 1, s >> 1));
    } else {
        if (k % m != m - 1 && (s & 2) == 0) {
            string v;
            v.push_back(value[k]);
            v.push_back(value[k + 1]);
            ret = max(ret, dpf(k + 2, s >> 2) + calValue(v));
        }
        string v;
        v.push_back(value[k]);
        v.push_back(value[k + m]);
        ret = max(ret, dpf(k + 1, (s >> 1) | (1 << (m - 1))) + calValue(v));
    }
    return ret;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        string tmp; cin >> tmp;  
        value += tmp;
    }
    memset(dp, -1, sizeof dp);
    printf("%d", dpf(0, 0));
}