自动搬运

查看原文

来自洛谷，原作者为

	woshishabi11451444 挨打就要立正，菜就要承认

搬运于2025-08-24 22:05:21，当前版本为作者最后更新于2024-08-27 10:21:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

考虑设计状态：

$dp_{i, j}$ 表示当前经过到第 $i$ 天，$n$ 件衣服需要洗的天数构成的集合为 $j$ 时的最大舒适度。

这里我们实现扩散型的转移：

$$dp_{i, j} \rightarrow dp_{i + 1, k} + z_{i + 1} \times y_v $$

其中 $k$ 表示当第 $i + 1$ 天穿第 $v$ 件衣服时 $n$ 件衣服需要洗的天数构成的集合，要保证第 $v$ 件衣服是可以穿的。

注意：每一天过后如果当一件衣服要洗，那么这件衣服需要洗的天数会 $-1$。

代码如下：

#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;
}