题解：P13513 [KOI 2025 #1] 釜山观光

lailai0916 · 2026-02-12 00:05:25 · 题解

题意简述

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