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

wyl123ly / 2024-09-24 / 原文

Problem link

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

状态设计

看到题目发现 $n\le4$ 则容易想到使用状态压缩dp，先设计状态 $dp_{j,i}$ 表示第 $i$ 天状态为 $j$ 时的最大舒适值。

但是这里的状态 $j$ 不能用以前的二进制来表示，注意到题目中还有一个限制条件“清洗时间”，则需要将这个“清洗时间”加入我们的状态设计当中。

发现题目条件中的 $y\le6$，则可以用七进制来表示状态 $j$，其中 $j$ 的第 $cnt$ 个进制位上的值代表到达这一天第 $cnt$ 件衣服还有几天清洗完成。

状态转移

状态设计完成，接下来考虑如何转移状态。

初始化：

显然 $dp_{0,0} = 0$，且 $dp$ 其他值初始化为极小值，这里极小值设置为-2e18。

这里很难通过 $j$ 状态去反推出之前的状态，则我们正推，用 $status$ 表示 $j$ 状态下往后一天推出的状态。

我们对于 $j$ 状态的第 $cnt$ 个进制位考虑：

设这个进制位的值为 $val$，

如果 $val$ 不为零，则 $status$ 的第 $cnt$ 个进制位上的值等于 $val - 1$，因为每过一天清洗时间就减少1。

如果 $val$ 为零，则先不管。

（因为 $val$ 为零代表可以在这一天选中这件衣服穿，而一天只能选择一件衣服，但是有可能有很多个 $val$ 为零的“待选衣服”）

代码：

int num = j;
while(num){
	if(num % 7 != 0) status += p(7,cnt) * ((num % 7) - 1);
	num /= 7;
	cnt++;
}

其中函数p是 $7^{cnt}$ 的意思。

接下来处理第 $cnt$ 个进制位上 $val$ 为零的情况：

如果我们选了这件衣服的话，状态 $status$ 会变成 $status+y_{cnt} \times 7^{cnt}$。

则对于每个 $val$ 为零的进制位上，可以得到转移 $dp$ 方程式：

dp[status + y[cnt + 1] * p(7,cnt)][i] = max(dp[status + y[cnt + 1] * p(7,cnt)][i],dp[j][i - 1] + z[i] * x[cnt + 1]);

寻找答案：

\[ans = \max^{7^n-1}_{j=0}\{dp_{j,m}\} \]

判断是否“如果必定有一天gcd没有衣服穿”：

根据数据范围设计一个上界，判断答案是否小于这个上界就可以了。

至此题目已经差不多做完了。

代码：

#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int MAXN = 2005;
const int INF = -2e18;
int n,m;
int x[MAXN],y[MAXN],z[MAXN];
int p(int a,int x){
	int ans = 1;
	for(int i = 1;i <= x;i++) ans *= a;
	return ans;
}
int dp[2505][MAXN];
void print(int x){
	for(int i = 1;i <= n;i++){
		cout<<x % 7;
		x /= 7;
	}
}
signed main(){
	cin>>n>>m;
	for(int i = 0;i <= MAXN - 2;i++){
		for(int j = 0;j <= MAXN + 500 - 2;j++){
			dp[j][i] = INF;
		}
	}
	for(int i = 1;i <= n;i++) cin>>x[i];
	for(int i = 1;i <= n;i++) cin>>y[i];
	for(int i = 1;i <= m;i++) cin>>z[i];
	dp[0][0] = 0;
	for(int i = 1;i <= m;i++){
		for(int j = 0;j <= p(7,n) - 1;j++){
			int status = 0;
			int num = j;
			int cnt = 0;
			while(num){
				if(num % 7 != 0) status += p(7,cnt) * ((num % 7) - 1);
				num /= 7;
				cnt++;
			}
			num = j;
			cnt = 0;
			for(int k = 1;k <= n;k++){
				if(num % 7 == 0) {
					dp[status + y[cnt + 1] * p(7,cnt)][i] = max(dp[status + y[cnt + 1] * p(7,cnt)][i],dp[j][i - 1] + z[i] * x[cnt + 1]);
				}
				num /= 7;
				cnt++;
			}
		}
	}
	int ans = INF;
	for(int j = 0;j <= p(7,n) - 1;j++){
		ans = max(ans,dp[j][m]);
	}
	if(ans == INF) cout<<"gcd loves her clothes!";
	else cout<<ans;
	return 0;
}