一道很裸的动态规划题。

算法思路

设状态 $f_i$ 表示前 $i$ 个异区间中，从第 1 个异区间到第 $i$ 个异区间最少需要消耗多少魂力。

我们枚举上一步是在哪个区间即可转移：

计算一下时间复杂度，发现一共有 $n$ 个状态，每个状态转移的时间复杂度为 $O(n)$ ，所以总时间复杂度为 $O(n^2)$ ，能通过本题。

代码

#include<bits/stdc++.h>
using namespace std;

#define LL long long

const LL N=3e3+10;

LL n,v[N],f[N];

int main(){
	scanf("%lld",&n);
	for(LL i=1;i<n;i++) scanf("%lld",&v[i]);
	memset(f,0x3f,sizeof(f));
	f[1]=0;
	for(LL i=2;i<=n;i++)
	{
		for(LL j=1;j<i;j++)
		{
			f[i]=min(f[i],f[j]+v[i-j]);
		}
	}
	printf("%lld",f[n]);
}