C. Mortal Kombat Tower（cf）dp

  Original link ：Problem - 1418C - Codeforces

The main idea of the topic ： There's a sequence n Number , Not 0 namely 1, There are two people , One is your friend , One is you . From left to right , Start with your friends , Everyone must choose one or two numbers at a time .ta After you choose, you choose again ta choose ... Ask your friend the minimum value of the last number .

1. In fact, let your friends get less 1, Get more 0;

2. use 0 Show your friend ,1 Show yourself . State shift ： use dp[i][0] Indicates the number of hits i Strange , And your friend finished it .dp[i][1] Indicates the number of hits i Strange , And you finished it .

2. State transition equation :

// If a friend takes this number , Just take a[i - 1] It was the last thing I took plus a[i] and a[i - 2] It was the last thing I took plus ..

dp[i][0] = min(dp[i - 1][1] + a[i], dp[i - 2][1] + a[i - 1] + a[i]); // The first number a friend takes, the second of the two numbers

dp[i][1] = min(dp[i - 1][0], dp[i - 2][0]);

AC Code ： 

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ios ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
typedef pair<int, int> PII;
const double pi = acos(-1.0);
#define rep(i, n) for (int i = 1; i <= (n); ++i)
#define rrep(i, n) for (int i = n; i >= (1); --i)
typedef long long ll;
#define sqar(x) ((x)*(x))

const int N = 2e5 + 10;
int dp[N][2]; // The first i When they are closed, they are taken by friends a[i] This value is also the minimum value of my friend when I take this value  0： friend  1 : I 
int a[N];

int main(){
  int n,t;
  cin >> t;
  while(t--){
    cin >> n;
    rep(i, n) cin >> a[i];
    dp[1][0] = a[1]; dp[1][1] = INF; // initialization 
    dp[2][0] = a[1] + a[2]; dp[2][1] = a[1]; //dp[i][0]、dp[i][1] Are the minimum values of friends , therefore dp[2][1] yes a[1] instead of a[2]                                                                                                      
    for(int i =3; i <= n; i++){
      dp[i][0] = min(dp[i - 1][1] + a[i], dp[i - 2][1] + a[i - 1] + a[i]); // Last time I chose one or two 
      dp[i][1] = min(dp[i - 1][0], dp[i - 2][0]);
    }
    cout << min(dp[n][0], dp[n][1]) << endl;
    }
    return 0;
}