【每日一题】树形dp专题 [AHOI2009]CHECKER 题解

Description

链接：https://ac.nowcoder.com/acm/problem/19884
来源：牛客网

在一个1行N列（N是奇数）的棋盘上，有K个格子是红色的。这种情况下，你有一个跳棋在最左端的格子上。你的目标是将它移动到最右边的格子，在开始移动之间，你可以在棋盘的任意空位上放棋子。在游戏开始后 你只可以随时在一个红色格子上放棋子。棋子的移动规则是：每次只可以选择一个棋子，跳过与之相邻的棋子走到后面的空格上，被它跳过的棋子被吃掉，即从棋盘上移走，如相邻棋子的另一侧有棋子，则不能跳。
请回答以下两个问题：
1：移动开始前至少要放多少棋子才能完成任务。
2：如果要使开始前放的棋子数要求尽量少，那么在移动过程中最少需要放多少个棋子才能完成任务。
关于规则的补充说明：
1：只能往空位上放棋子，不管是移动开始前还是移动过程中。
2：移动前棋盘最左端的那个原始棋子绝对不能被吃掉.

Solution

分类讨论

• 没有出现两个红色的格子相邻的情况
  在每个偶数的位置放置棋子，能以最少的代价到达终点。

• 出现了两个红色的格子相邻的情况
  考虑以下图片：
  
  可以通过两个红色的格子无限延伸，所以第一问的答案为0
  第二问我们可以动态规划解决：
  令 为到达 点的最小代价
  由于可以往前跳和往后跳，所以

• 

• 
  时间复杂度

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
typedef long long ll;
ll dp[1005]; 
int a[1005], cnt[1005];
int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);
  int n; cin >> n;
  for(int i = 1; i <= n; i++) cin >> a[i];
  a[1] = 0; // 第一个点是红是白没有区别，不能影响后续判断
  bool flag = false;
  for(int i = 1; i <= n; i++) {
    if(i % 2 == 0) cnt[a[i]]++;
    if(a[i] + a[i - 1] == 2) {
      flag = true;
    }
  }
  if(!flag) {
    cout << cnt[0] << '\n';
    cout << cnt[1] << '\n';
  } else {
    cout << 0 << '\n'; // 有两个连续的1 可以交替跳
    for(int i = 1; i <= n; i++) {
      if(a[i]) dp[i] = 1;
      else dp[i] = 1e18;
    }
    for(int i = 1; i <= n; i++) {
      for(int j = i - 2; j >= 1; j--) {
        dp[j] = min(dp[j], dp[j + 1] + dp[j + 2]);
      }
      for(int j = i + 2; j <= n; j++) {
        dp[j] = min(dp[j], dp[j - 1] + dp[j - 2]);
      }
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++) {
      if(i % 2 == 0) {
        ans += dp[i];
      }
    }
    cout << ans << '\n';
  }
  return 0;
}