P13513 釜山观光题解

此题考察的是动态规划（DP）问题。这种问题通常分为三步：状态定义，数组初始化以及状态转移。

### 状态定义
令 $dp_{i,j}$ 表示覆盖 Hankook 前 $i$ 天和 Jeong-ul 前 $j$ 天观光的最小费用。

### 数组初始化

如果 Jeong-ul 没有参观，即 $dp_{i,0}$，则此时其值应该为买一日票，三日票，五日票的最小值，不需要考虑组合票。

同理可以得到 Hankook 没有参观的初始化。

### 状态转移
为了表达方便，我们记一日票的价格为 $p_1$，三日票价格为 $p_3$，五日票价格为 $p_5$，组合票价格为 $p_{pair}$。

对于每一天 $(i,j)$，我们考虑以下购买方式：

- 购买一日票：
  - 如果 Hankook 第 $i$ 天观光，购买一日票，有：
    
  $$
  dp_{i,j}=\min(dp_{i,j},dp_{i-1,j}+p_1)
  $$
   - 如果 Jeong-ul 第 $j$ 天观光，购买一日票，有：
     
  $$
  dp_{i,j}=\min(dp_{i,j},dp_{i,j-1}+p_1)
  $$

同理，我们也可以推出购买三日票，五日票以及组合票的状态转移方程：

- 购买三日票：
  - 如果 Hankook 第 $i$ 天观光，购买三日票，有：

$$
  dp_{i,j}=\min(dp_{i,j},dp_{\max(i-3,0),j}+p_3)
  $$
  - 如果 Jeong-ul 第 $j$ 天观光，购买三日票，有：
  
  $$
  dp_{i,j}=\min(dp_{i,j},dp_{i,\max(j-3,0)}+p_3)
  $$

这里要注意，因为是三日票，所以应该覆盖了 $3$ 天，$i$ 应当要减去 $3$。但若 $i\le2$，数组可能会产生越界，要记得与 $0$ 取最大值。$j$ 同理。

五日票和组合票的状态转移方程，请读者自行推导，与三日票的方程是相似的。

最后的结果就是 $dp_{n,n}$，即他们两人都观光了 $n$ 天所需费用的最小值。

### 参考代码

虽然状态转移比基础的动态规划稍长，但逻辑全部是相同的，很容易理解。

```cpp
//初始化
for(int i=1;i<=n;i++)
    dp[i][0]=min({dp[i-1][0]+p1*(ch1[i]=='1'),dp[max(0,i-3)][0]+p3,dp[max(0,i-5)][0]+p5});
for(int i=1;i<=n;i++)
    dp[0][i]=min({dp[0][i-1]+p1*(ch2[i]=='1'),dp[0][max(0,i-3)]+p3,dp[0][max(0,i-5)]+p5});
//状态转移
for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        dp[i][j]=dp[i-1][j]+(ch1[i]=='1')*p1,dp[i][j]=min(dp[i][j],dp[i][j-1]+(ch2[j]=='1')*p1);
        dp[i][j]=min(dp[max(0,i-3)][j]+p3,dp[i][j]),dp[i][j]=min(dp[i][max(0,j-3)]+p3,dp[i][j]);
        dp[i][j]=min(dp[max(0,i-5)][j]+p5,dp[i][j]),dp[i][j]=min(dp[i][max(0,j-5)]+p5,dp[i][j]);
        if(i==j) dp[i][j]=min(dp[max(0,i-4)][max(0,j-4)]+p_pair,dp[i][j]);
    }
}
```

正在渲染内容...

P13513 釜山观光 题解