P4928 [MtOI2018]衣服？身外之物！ 题解

题意

gcd 共有 \(n\) 件衣服，编号为 \(A_1,A_2,\cdots A_n\)。

每一件衣服分别拥有颜色值和清洗时间，他在每一件衣服穿完以后都会将其送去清洗，而这件衣服当天所拥有的舒适感取决于当天的天气与他的衣服颜色值的乘积，天气值存在负数。

现给出共 \(m\) 天的天气情况，求最大舒适值。

分析

数据范围极小，考虑状压。

设当前状态为 \(f_{i, j}\) 表示已经过完了第 \(i\) 天，过完第 \(i\) 天之后的衣服状态为 \(j\)。其中 \(j\) 是一个 \(7\) 进制数，它的第 \(k\) 位表示第 \(k\) 件衣服还需要洗几天。（若 \(j = 0\)，则表示不需要洗了，可以直接用。）

由于本人比较懒，因此直接用了十进制数代替七进制。（因此拿到了最劣解）。

总状态数最劣为 \(O(m \times \prod y_i)\) 个，在题目数据范围内可过。为了加速，可以提前处理出可用状态。

代码示例

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define rep(i, a, b) for (int i = (a); i <= (b); i ++ )

using namespace std;

using LL = long long;
const int N = 2010;

int n, m;
int c[N], t[N], w[N];
LL f[N][7000];
vector<int> state;

int get(int x, int k) { // 取出 x 的第 k 位
    int res; while (k) res = x % 10, x /= 10, k -- ;
    return res;
}

bool check(int s) { // 判断状态 s 是否可用
    //  判断条件：1. 没有一位大于它最大的清洗时间
    //  2. 必须有至少以为是 0，否则 gcd 将没有衣服穿
    for (int i = 1; i <= n; i ++ ) if (get(s, i) > t[i]) return false;
    for (int i = 1; i <= n; i ++ ) if (!get(s, i)) return true;
    return false;
}

int modify(int s, int k) { // 改动 s 的第 k 位
    //  即：其他衣服的清洗时间 - 1，第 k 天的重置位 t[k]
    int ans = 0;
    for (int i = n; i; i -- )
        if (i == k) ans = ans * 10 + t[k];
        else ans = ans * 10 + (get(s, i) > 0 ? get(s, i) - 1 : 0);
    return ans;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
        scanf("%d", &c[i]);
    for (int i = 1; i <= n; i ++ )
        scanf("%d", &t[i]);
    for (int i = 1; i <= m; i ++ )
        scanf("%d", &w[i]);
    
    for (int i = 0; i < pow(10, n); i ++ ) // 枚举可用状态
        if (check(i))
            state.push_back(i); // 并存储
	
    memset(f, -0x7f, sizeof f);
    f[0][0] = 0;
    for (int i = 0; i < m; i ++ )
        for (auto j : state)
            for (int k = 1; k <= n; k ++ )
                if (f[i][j] != -0x7f7f7f7f && !get(j, k))
                    f[i + 1][modify(j, k)] = max(f[i + 1][modify(j, k)], f[i][j] + w[i + 1] * c[k]);
    
    LL res = -0x7f7f7f7f;
    for (auto i : state)
        res = max(res, f[m][i]);
    if (res == -0x7f7f7f7f) puts("gcd loves her clothes!");
    else printf("%lld\n", res);

    return 0;
}