P13513

[KOI 2025 #1] 釜山观光

题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

釜山广域市为了方便游客的交通出行，销售以下几种交通票券。

类别	使用人数	有效期	价格	备注
1 日票	1 人	购买当天，共 1 天	$p_1$	有效期内仅限购买者本人使用
3 日票	1 人	含购买当天在内的连续 3 天	$p_3$	有效期内仅限购买者本人使用
5 日票	1 人	含购买当天在内的连续 5 天	$p_5$	有效期内仅限购买者本人使用
组合票	2 人	含购买当天在内的连续 4 天	$p_{pair}$	有效期内两人均可使用

所有票券均在购买后立即生效，并可在票券上标明的有效期内使用交通工具。当然，即使持有票券但未使用交通工具，或持有多张有效期重叠的票券，或票券的有效期超出了 N 天的观光行程也都是允许的。另外请注意， $p_1 \le p_3 \le p_5$ 这一关系并非总是成立。

Hankook 和 Jeong-ul 将在釜山一同停留 $N$ 天。但是，两人各自制定了自己的观光计划，并决定了每天自己是否要进行观光。为了完成观光行程，对于每个人，在他们进行观光的每一天，都必须持有一张有效的票券（包括组合票）。

例如，假设 $N=9$ ， $p_1=3, p_3=7, p_5=12, p_{pair}=15$ ，Hankook 和 Jeong-ul 各自的日程如下：

日期	1	2	3	4	5	6	7	8	9
Hankook	X	O	O	X	O	O	O	X	O
Jeong-ul	O	O	X	X	X	O	O	O	X

(O 代表观光，X 代表不观光)

如果只使用 1 日票，总观光天数为 11 天 (Hankook 6 天 + Jeong-ul 5 天)，费用为 11 (观光天数) × 3 (1 日票价格) = 33。

但是，如果两人在第 5 天至第 8 天共享一张组合票，总费用仅为 30。

更有甚者，如果 Hankook 购买一张第 5 天至第 7 天的 3 日票，Jeong-ul 购买一张第 6 天至第 8 天的 3 日票，总费用可以节省至 29。

当 Hankook 的日程由字符串 $A = A_1A_2\cdots A_N$ 表示，Jeong-ul 的日程由字符串 $B = B_1B_2\cdots B_N$ 表示时，对于日期 $i(1 \le i \le N)$ :

如果 Hankook 进行观光， $A_i=1$ ；否则 $A_i=0$
如果 Jeong-ul 进行观光， $B_i=1$ ；否则 $B_i=0$

请根据以上形式给出的日程，编写一个程序，计算出为了确保在每个人进行观光的每一天都持有至少一张有效票券（包括组合票）所需的最少费用。

输入格式

第一行给定一个表示在釜山停留时间的整数 $N$ 。

第二行给定一个表示 Hankook 日程的字符串 $A$ 。

第三行给定一个表示 Jeong-ul 日程的字符串 $B$ 。

第四行给定 $p_1, p_3, p_5, p_{pair}$ ，以空格分隔。

输出格式

在第一行输出表示最小费用的整数。

输入输出样例

输入样例 #1

输出样例 #1

输入样例 #2

9
011011101
110001110
1 10000 10000 10000

输出样例 #2

说明/提示

限制条件

给定的所有数都是整数。
$1 \le N \le 2000$ 。
字符串 $A, B$ 的长度均为 $N$ ，且所有字符均为 0 或 1。
$1 \le p_1, p_3, p_5, p_{pair} \le 10000$ 。

子任务

(6 分) $p_1 = 1$ ， $p_3 = p_5 = p_{pair} = 10000$ 。
(12 分) $p_{pair} = 1$ ， $p_1 = p_3 = p_5 = 10000$ 。
(16 分) 对于所有 $i(1 \le i \le N)$ ，都有 $A_i = B_i = 1$ 。
(24 分) 对于所有 $i(1 \le i \le N)$ ，都有 $B_i = 0$ 。
(42 分) 无附加限制条件。

题解

1 篇题解

登录后即可使用 Markdown 发布题解。

YuyiLv.6👑 站长管理员

P13513 [KOI 2025 1] 釜山观光题解 Author: Yuyi 题意分析两人在釜山观光 $N$ 天。每天可以选择游玩或者不游玩。有四种票：1日票、3日票、5日票（均为单人票），以及4日双人组合票。要求在两人所有“游玩”的日子里，都必须持有有效的票。票的有效期可以重叠，也可以超出 $N$ 天。价格的大小关系也不一定遵循天数越长越贵的规…

点击展开完整题解点击收起题解

2026年8月9日 22:36

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

Author: Yuyi

题意分析

两人在釜山观光 $N$ 天。每天可以选择游玩或者不游玩。有四种票：1日票、3日票、5日票（均为单人票），以及4日双人组合票。要求在两人所有“游玩”的日子里，都必须持有有效的票。票的有效期可以重叠，也可以超出 $N$ 天。价格的大小关系也不一定遵循天数越长越贵的规律。求两人都满足条件的最小总花费。

部分分解法与暴力代码

对于特殊的 Subtask：

如果只有 1 日票便宜，其他票极贵，那么答案就是两人游玩天数之和 $\times p_1$ 。
如果只有组合票便宜，那么可以考虑每隔 4 天买一张组合票。如果强制写一个纯暴力的 DFS（枚举每一天每个人买什么票），每个需要票的日子都有数十种买票组合，时间复杂度是指数级，只能通过极小的数据（如 $N \le 10$ ）。

正解推导过程与转移方程

题目明确给定了多日票的覆盖天数较小（最长只有 5 天）。本题时限内存给足了1GB，我们可以直接毫无顾忌地开启一个五维 DP 数组。即 f[i][j][k][l][m]：

i：Hankook 当前所处的天数 ( $1 \le i \le N$ )
j：Jeong-ul 当前所处的天数 ( $1 \le j \le N$ )
k：Hankook 的单人票剩余有效天数（不含今天，取值 0~4）
l：Jeong-ul 的单人票剩余有效天数（不含今天，取值 0~4）
m：双人组合票剩余有效天数（不含今天，取值 0~3） 状态转移方程： 由于两人是同步在釜山度过每一天的，在第 i 和 j 天进行决策时（实际中 $i==j$ ）：

检查两人今天是否已经有票覆盖（依靠各自单人票剩余或组合票剩余）。
如果两人都不需要在今天买票（要么不游玩，要么已有覆盖），则不买票直接转移到明天： $f[i][j][k][l][m] = f[i+1][j+1][\max(0,k-1)][\max(0,l-1)][\max(0,m-1)]$
如果今天某人游玩且没有票覆盖，则必须买票。此时枚举 17 种买票方案（设某方案花费为 $cost$ ，能带来新的剩余天数为 $nk, nl, nm$ ）： $f[i][j][k][l][m] = \min_{\text{合法方案}} \{ cost + f[i+1][j+1][nk][nl][nm] \}$

正解代码及分析

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-9
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dep(i,a,b) for(int i=(a);i>=(b);i--)
#define lowbit(a) (a)&(-a)
using namespace std;
const int maxn = 2005;
const int mo = 998244353;
const double pi = acos(-1.0);
template <typename T>
inline void read(T &X)
{
    X = 0;int w = 0; char ch = 0;
    while(!isdigit(ch)) {w |= ch == '-' ;ch = getchar();}
    while(isdigit(ch)) X = X * 10 + (ch^48),ch = getchar();
    if(w) X = -X;
}
int n;
string A,B;
int p1,p3,p5,ppair;
int f[maxn][maxn][5][5][4]; //内存有1GB，直接开满真正的五维数组
struct Buy
{
    int hc,jc,cost;
};
vector<Buy> vec;
void init()
{
    int hc[] = {0,1,3,5};
    int hcst[] = {0,p1,p3,p5};
    int jc[] = {0,1,3,5};
    int jcst[] = {0,p1,p3,p5};
    rep(x,0,3) rep(y,0,3) vec.push_back({hc[x],jc[y],hcst[x]+jcst[y]});
    vec.push_back({4,4,ppair}); //组合票覆盖4天
}
int dfs(int i,int j,int k,int l,int m)
{
    if(i > n && j > n) return 0;
    if(f[i][j][k][l][m] != -1) return f[i][j][k][l][m];
    bool h_ok = (k > 0 || m > 0);
    bool j_ok = (l > 0 || m > 0);
    bool h_need = (A[i-1] == '1' && !h_ok);
    bool j_need = (B[j-1] == '1' && !j_ok);
    if(!h_need && !j_need)
    {
        int nk = max(0,k-1);
        int nl = max(0,l-1);
        int nm = max(0,m-1);
        return f[i][j][k][l][m] = dfs(i+1,j+1,nk,nl,nm);
    }
    int ans = inf;
    for(auto cur : vec)
    {
        bool nh_ok = h_ok || (cur.hc > 0);
        bool nj_ok = j_ok || (cur.jc > 0);
        if(A[i-1] == '1' && !nh_ok) continue;
        if(B[j-1] == '1' && !nj_ok) continue;
        int nk = max(0,k-1);
        int nl = max(0,l-1);
        int nm = max(0,m-1);
        if(cur.hc == 3) nk = max(nk,2);
        if(cur.hc == 5) nk = max(nk,4);
        if(cur.jc == 3) nl = max(nl,2);
        if(cur.jc == 5) nl = max(nl,4);
        if(cur.hc == 4) nm = max(nm,3);
        ans = min(ans,cur.cost+dfs(i+1,j+1,nk,nl,nm));
    }
    return f[i][j][k][l][m] = ans;
}
void solve()
{
    read(n);
    cin >> A >> B;
    read(p1),read(p3),read(p5),read(ppair);
    init();
    rep(i,1,n+1) rep(j,1,n+1) rep(k,0,4) rep(l,0,4) rep(m,0,3) f[i][j][k][l][m] = -1;
    cout << dfs(1,1,0,0,0) << endl;
    return;
}
int main()
{
    int T=1;
//  freopen("mul.in","r",stdin);
//  freopen("mul.out","w",stdout);
//  read(T);
    while(T--) solve();
    return 0;
}

复杂度分析

时间复杂度：有效状态总数为 $N \times 5 \times 5 \times 4 = 100N$ 个。在每个状态中最多只会枚举 $17$ 种购票方案。对于 $N \le 2000$ 的数据， $O(100N \times 17) \approx 3.4 \times 10^6$ 次计算，轻松通过。
空间复杂度：五维数组 $2005 \times 2005 \times 5 \times 5 \times 4$ （类型为 int），总计消耗约 $1.6 \text{ GB}$ 的内存。如果你的评测机严格限制了 1GB 或更小的内存导致 MLE，请务必使用下方的空间优化代码。

空间优化解法与代码（解决 MLE）

如前文推导所述，由于两人是同步在釜山度过每一天的，在逐天递推的过程中 i 永远等于 j。所以我们根本不需要在状态里同时存储 i 和 j，造成 $N^2$ 的空间浪费。我们可以直接将前两维合并，用 f[i][k][l][m] 来表示“两人共同处在第 i 天”时的状态。这只需改动极少部分，就能把空间复杂度降为 $O(N)$ ，将内存从 1.6 GB 暴降至不到 1 MB！

优化后的转移方程： $f[i][k][l][m] = \min_{\text{合法方案}} \{ cost + f[i+1][nk][nl][nm] \}$

优化版代码（4D 数组）：

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-9
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dep(i,a,b) for(int i=(a);i>=(b);i--)
#define lowbit(a) (a)&(-a)
using namespace std;
const int maxn = 2005;
const int mo = 998244353;
const double pi = acos(-1.0);
template <typename T>
inline void read(T &X)
{
    X = 0;int w = 0; char ch = 0;
    while(!isdigit(ch)) {w |= ch == '-' ;ch = getchar();}
    while(isdigit(ch)) X = X * 10 + (ch^48),ch = getchar();
    if(w) X = -X;
}
int n;
string A,B;
int p1,p3,p5,ppair;
int f[maxn][5][5][4]; //降掉无用的j维度，完美解决MLE
struct Buy
{
    int hc,jc,cost;
};
vector<Buy> vec;
void init()
{
    int hc[] = {0,1,3,5};
    int hcst[] = {0,p1,p3,p5};
    int jc[] = {0,1,3,5};
    int jcst[] = {0,p1,p3,p5};
    rep(x,0,3) rep(y,0,3) vec.push_back({hc[x],jc[y],hcst[x]+jcst[y]});
    vec.push_back({4,4,ppair});
}
int dfs(int i,int k,int l,int m)
{
    if(i > n) return 0;
    if(f[i][k][l][m] != -1) return f[i][k][l][m];
    bool h_ok = (k > 0 || m > 0);
    bool j_ok = (l > 0 || m > 0);
    bool h_need = (A[i-1] == '1' && !h_ok);
    bool j_need = (B[i-1] == '1' && !j_ok);
    if(!h_need && !j_need)
    {
        int nk = max(0,k-1);
        int nl = max(0,l-1);
        int nm = max(0,m-1);
        return f[i][k][l][m] = dfs(i+1,nk,nl,nm);
    }
    int ans = inf;
    for(auto cur : vec)
    {
        bool nh_ok = h_ok || (cur.hc > 0);
        bool nj_ok = j_ok || (cur.jc > 0);
        if(A[i-1] == '1' && !nh_ok) continue;
        if(B[i-1] == '1' && !nj_ok) continue;
        int nk = max(0,k-1);
        int nl = max(0,l-1);
        int nm = max(0,m-1);
        if(cur.hc == 3) nk = max(nk,2);
        if(cur.hc == 5) nk = max(nk,4);
        if(cur.jc == 3) nl = max(nl,2);
        if(cur.jc == 5) nl = max(nl,4);
        if(cur.hc == 4) nm = max(nm,3);
        ans = min(ans,cur.cost+dfs(i+1,nk,nl,nm));
    }
    return f[i][k][l][m] = ans;
}
void solve()
{
    read(n);
    cin >> A >> B;
    read(p1),read(p3),read(p5),read(ppair);
    init();
    rep(i,1,n+1) rep(k,0,4) rep(l,0,4) rep(m,0,3) f[i][k][l][m] = -1;
    cout << dfs(1,0,0,0) << endl;
    return;
}
int main()
{
    int T=1;
//  freopen("mul.in","r",stdin);
//  freopen("mul.out","w",stdout);
//  read(T);
    while(T--) solve();
    return 0;
}

Generated by Gemini 3.1 Pro

讨论

0 条讨论

登录后即可使用 Markdown 发起讨论和回复。

还没有讨论，来发起第一条吧。