The solution of「AT_kupc2021_c Gacha」

· · 题解

\textup{AT kupc2021c Gacha}

\textup{Link} | 更好体验 | \textup{Tag: }贪心，dp。

\textup{Solution}

> 由于给定位置升序，考虑一个贪心，如果 $a_i$ 对应的不是 $b_i$ 而是 $b_{i + 1}$，感性理解交叉着选的一定不如直接对应优秀。 > > 故 $a_i$ 的硬币一定是从 $b_i$ 取来的。 $\textup{Step2}$：哪些位置的硬币和游戏机对是不用考虑的？ > 因为从 $0$ 出发，于是我们钦定终点在最后一个游戏机（硬币）位置。 > > 如果硬币在它所属游戏机的前面，那我们先遇到它再游玩是不需要额外计算代价的。 > > 于是问题就变成了如果硬币在游戏机后面，应该在一个什么策略下迂回游玩。 $\textup{Step3}$：这很 dp。 > 设 $dp_i$ 表示到第 $i$ 个游戏机游玩完的最小代价。 > > 考虑一个暴力转移： > > $$ > dp_i = \min_{j = 1}^{j < i} dp_j + 2 b_i - 2 a_{j + 1} > $$ > > 注：此处枚举的 $j$ 是上一个已经游玩完毕的 $j$。 $\textup{Step4}$：优化。 > 上面式子中 $2 b_i$ 是常数，于是对于每一个 $j$ 我们单独记录前缀 $dp_j + 2b_j$ 的最小值，就可以优化到 $O(1)$。 > > 然而最后的答案并不是 $dp_N$，因为我们这样 dp 做出来的其实是需要回到后面那个硬币点的代价。 > > 但是最后一次并不需要回到硬币点，于是要单独对于每一个点作停下位置统计答案便做完啦，复杂度 $O(N)$。 --- ## $\textup{Code}

\textup{Submission.}

int N, cnt;
int a[MAXN], b[MAXN], dp[MAXN];
void slove(){
    cin >> N;
    for( int i = 1; i <= N; i ++ ) cin >> a[i];
    for( int i = 1; i <= N; i ++ ){
        cin >> b[i]; b[i] = max( a[i], b[i] );//只用计算要迂回的
    }
    int minn = - 2 * a[1];//前缀最小值
    for( int i = 1; i <= N; i ++ ){
        dp[i] = minn + b[i] * 2;
        minn = min( minn, dp[i] - 2 * a[i + 1] );
    }
    int ans = dp[N];
    for( int i = 0; i < N; i ++ )//对于每个点统计答案
        ans = min( ans, dp[i] + b[N] - a[i + 1] );
    cout << ans + b[N] << endl;//不输出换行判定会 WA
}

\textup{Last}

审核管理员辛苦了，如果您有所疑惑或我有所错漏，请您在评论区指出或找我，我会一定解答并且修改本题解。

如果您觉得本文写的还不错，那可以留个赞吗？

谢谢你看到这里~