P13513 [KOI 2025 #1] 釜山观光

题意简述

Hankook 和 Jeong-ul 两个人将在釜山停留 $n$ 天，给定两个 $\texttt{01}$ 字符串 $a,b$ 表示各自日程。

若某人某天对应的日程字符为 $\texttt{1}$，则该人当天必须拥有至少一张有效票券。

可购买以下票券，求所需的最小费用：

• 单人 $1$ 日票，价格 $p_1$；
• 单人 $3$ 日票，价格 $p_3$；
• 单人 $5$ 日票，价格 $p_5$；
• 双人 $4$ 日票，价格 $p_\text{pair}$。

解题思路

考虑使用 DP 解决：设 $f_{i,j}$ 表示 Hankook 前 $i$ 天和 Jeong-ul 前 $j$ 天都满足覆盖的最小费用。

边界情况 $f_{0,0}=0$。

枚举 $f_{i,j}$，考虑三种情况的最小值：

1. 覆盖 Hankook：$\min\set{f_{i-1,j}+[a_i=\texttt{1}]p_1,f_{i-3,j}+p_3,f_{i-5,j}+p_5}$；
2. 覆盖 Jeong-ul：$\min\set{f_{i,j-1}+[b_j=\texttt{1}]p_1,f_{i,j-3}+p_3,f_{i,j-5}+p_5}$；
3. 两人同时覆盖（$i=j$）：$f_{i-4,j-4}+p_\text{pair}$。

时间复杂度为 $O(n^2)$。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int inf=0x3f3f3f3f;
const int N=2005;
int f[N][N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,p1,p3,p5,pr;
	string a,b;
	cin>>n>>a>>b>>p1>>p3>>p5>>pr;
	memset(f,0x3f,sizeof f);
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=n;j++)
		{
			if(i==0&&j==0){f[i][j]=0;continue;}
			int t1=i==0?inf:min({f[i-1][j]+(a[i-1]-'0')*p1,f[max(0,i-3)][j]+p3,f[max(0,i-5)][j]+p5});
			int t2=j==0?inf:min({f[i][j-1]+(b[j-1]-'0')*p1,f[i][max(0,j-3)]+p3,f[i][max(0,j-5)]+p5});
			int t3=i!=j?inf:f[max(0,i-4)][max(0,j-4)]+pr;
			f[i][j]=min({t1,t2,t3});
		}
	}
	cout<<f[n][n]<<'\n';
	return 0;
}