题解 P2039 [AHOI2009]跳棋
Иɔlɔ
·
·
题解
考虑到所有偶数点都有棋子那么一定能跳到最右边。
第一问
考虑三种情况：
- 有不少于两个红格子连着。可以一直在行动中放，从而到达任意一个格子，过程可自行模拟。第一问答案为 0。注意连着的两个红格子不能有 1。
- 一个白格子一个红格子。在红格子上放一个棋子就可以用白格子上的棋子跳过去，代价为 1。
- 两个白格子，在偶数点上放是最优的，代价为 1。
累加这几种情况的答案即可。
第二问
- 如果这个点能被红格子上的棋子跳到，从红格子去跳。
- 如果不能，就放棋子。
如果只有一个情况为第一种情况，可以暴力更新。
否则，求这个点被跳到的最小代价。发现第一种情况的代价是斐波那契数列，从左至右从右至左各更新一次即可。
时间复杂度 O(n)。
```cpp
const int N = 1005;
int n, x, cnt;
ll dp[N];
ll inf, sum;
int main() {
memset(dp, 0x3f, sizeof dp);
inf = dp[1];
qread(n, x);
rep(i, 2, n) { // for(int i = 2; i <= n; i++)
qread(x);
if(x) dp[i] = 1;
}
rep(i, 2, n) To_min(dp[i], dp[i - 1] + dp[i - 2]);
per(i, n, 2) To_min(dp[i], dp[i + 1] + dp[i + 2]); // for(int i = n; i >= 2; i--)
for(int i = 2; i <= n; i += 2) dp[i] == inf ? ++cnt : sum += dp[i];
printf("%d\n%lld\n", cnt, sum);
return 0;
}
```