C. Mortal Kombat Tower（DP）

题目传送门

Mortal Kombat Tower

题目大意

你和你朋友打游戏，给你一个长度为n的数组代表boss，数组中包含0和1，你朋友先手 你可以打败任意boss而不消耗值，你朋友在打败1的boss时需要消耗1，每次可以选择打败1~2个boss 求最小的通关花费

思路

开两个一维数组，分别为你朋友杀了第i个怪物需要的最小花费，你杀了第i个怪物的最小花费，可得 $dp1[i]=min(dp2[i-1],dp2[i-2])$ $dp2[i]=min(dp1[i-1]+a[i],dp1[i-2]+a[i]+a[i-1])$ 将dp1代入dp2中，可得 $dp[i]=min(min(dp[i-2],dp[i-3])+a[i],min(dp[i-3],dp[i-4])+a[i]+a[i-1])$ 初始化时为： $dp[1]=a[1],dp[2]=a[1]+a[2],$ $dp[3]=dp[1]+a[3],dp[4]=min(min(dp[2],dp[1])+a[4],dp[1]+a[3]+a[4])$ 最后通过时需要从$dp[n],dp[n-1],dp[n-2]$中取最小值，因为可能是我杀一个或者两个，可能是朋友杀的

AC Code

#include<cstdio> #include<algorithm> #include<iostream> #include<cstring> using namespace std; #define endl '\n' #define INF 0x3f3f3f3f #define int long long #define debug(a) cout<<#a<<"="<<a<<endl; // #define TDS_ACM_LOCAL const int N=2e5 +9; int n, a[N]; int dp[N]; void solve(){ cin>>n; for(int i=1; i<=n; i++) cin>>a[i]; if(n==1 || n==2) {cout<<a[1]<<endl; return ;} dp[1]=a[1], dp[2]=a[1]+a[2]; dp[3]=dp[1]+a[3], dp[4]=min(min(dp[2],dp[1])+a[4], dp[1]+a[3]+a[4]); for(int i=5; i<=n; i++) dp[i]=min( min(dp[i-2], dp[i-3]) +a[i], min(dp[i-3], dp[i-4]) +a[i] +a[i-1]); cout<<min(min(dp[n], dp[n-1]), dp[n-2])<<endl; return ; } signed main(){ ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); #ifdef TDS_ACM_LOCAL freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin); freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout); #endif int T; cin>>T; while(T--) solve(); return 0; }