mayoko’s diary

プロコンとかいろいろ。

すぬけのお誕生日コンテスト C - Supermarket

解法

bitDP します。

dp[s] = (s で表される集合は既に優先順位が上になることが決まっていて, 新しく別の種類の食品を食べることが出来ないと決まっている月である時, まだ追加することの出来る食品の種類の数) とします。

mask[i] = (食品 i が売られている月のフラグ)とすると, (s|mask[i]) > s である時, i 種類目の食品を一番優先して食べれる月が存在するということなので, dp[s] = max(dp[s], dp[s|mask[i]]+1) という漸化式を解けば良いです。

const int MAXN = 10010;
int mask[MAXN];
int dp[1<<12];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < 12; j++) if (s[j] == 'o') mask[i] |= 1<<j;
    }
    for (int s = (1<<12)-1; s >= 0; s--) {
        for (int i = 0; i < n; i++) {
            if ((s|mask[i]) > s) {
                dp[s] = max(dp[s], 1+dp[s|mask[i]]);
            }
        }
    }
    cout << dp[0] << endl;
    return 0;
}