题解：P4928 [MtOI2018] 衣服？身外之物！
违规用户名576639
·
·
题解
考虑设计状态：
这里我们实现扩散型的转移：
$$dp_{i, j} \rightarrow dp_{i + 1, k} + z_{i + 1} \times y_v$$
其中 $k$ 表示当第 $i + 1$ 天穿第 $v$ 件衣服时 $n$ 件衣服需要洗的天数构成的集合，要保证第 $v$ 件衣服是可以穿的。
注意：每一天过后如果当一件衣服要洗，那么这件衣服需要洗的天数会 $-1$。
代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5;
const int M = 8;
const long long inf = 1e10;
const long long INF = 5e15;
int n, m, a[M], x[N], y[N], z[N], power[N];
long long dp[N][M * M * M * M];
int main(){
cin >> n >> m;
power[0] = 1;
for(int i = 1; i <= n; i++){
power[i] = power[i - 1] * 7;
}
for(int i = 0; i < n; i++){
cin >> x[i];
}
for(int i = 0; i < n; i++){
cin >> y[i];
}
for(int i = 1; i <= m; i++){
cin >> z[i];
}
for(int i = 0; i <= m; i++){
for(int j = 0; j < power[n]; j++) dp[i][j] = -INF;
}
dp[0][0] = 0;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++) a[j] = 0;
for(int j = 0; j < power[n]; j++){
if(j > 0) a[0]++;
for(int i = 0; i < n && a[i] >= 7; a[i] -= 7, a[++i]++);
int num = 0;
for(int i = 0; i < n; i++) num += max(0, a[i] - 1) * power[i];
for(int k = n - 1; k >= 0; k--){
if(!a[k]){
int v = num + y[k] * power[k];
dp[i + 1][v] = max(dp[i + 1][v], dp[i][j] + x[k] * z[i + 1]);
}
}
}
}
long long ans = -INF;
for(int i = 0; i < power[n]; i++){
ans = max(ans, dp[m][i]);
}
if(ans < -inf){
cout << "gcd loves her clothes!";
return 0;
}
cout << ans;
return 0;
}
```