你是DEEP国的大军师，辅佐一个非常有野心的国王，这位国王非常有野心，他计划攻占 n 个国家。在地图上，这些国家排成一行。
探子已经查明，当攻打一个国家 i 时，为了防止国家间的联合对抗，需要给该国家周围，所有未被攻占的国家支付 c o s t i cost_i costi个金币，即对于国家 i i i，它左侧第一个已被攻打的国家为 l l l，右侧第一个已被攻打的国家为 r r r，则他需要给 [ l + 1 , i − 1 ] [l+1,i-1] [l+1,i−1] 和 [ i + 1 , r − 1 ] [i+1,r-1] [i+1,r−1]之间的国家支付金币。如果 l l l 不存在，则需要给 [ 1 , i − 1 ] [1, i-1] [1,i−1] 之间的所有国家支付金币；若 r r r 不存在，则需要给 [ i + 1 , n ] [i+1,n] [i+1,n] 之间的所有国家支付金币。
现在，你的下属已经给你提供了每个国家需要支付金币的数量。为了满足国王的野心，你需要计算出攻占完所有国家需要的最小花费。
输入 第一行是一个整数 T，代表接下来有T组数据。 接下来每组数据 第一行有一个整数 n，代表要攻占的国家数目。 第二行共 n 个整数，代表攻占每个国家前，需要支付给其周围未被攻占国家 c o s t i cost_i costi个金币。
输出 对于每组数据输出一行，代表需要支付的最小花费。
样例 输入
2 1 1 3 1 1 2
输出
0 2
题解 区间dp,但是打重现赛的时候因为自己太久没写区间dp了，实在是想不起了，无语~
代码
#include <iostream> #include <algorithm> #include <cstdio> #include <queue> #include <cmath> #include <string> #include <cstring> #include <map> #include <set> #include <cmath> using namespace std; #define me(x,y) memset(x,y,sizeof x) #define MIN(x,y) x < y ? x : y #define MAX(x,y) x > y ? x : y typedef long long ll; const int maxn = 2e5+10; const int INF = 0x3f3f3f3f; const int MOD = 998244353; const double eps = 1e-06; const double PI = acos(-1.0); int main(){ int t; cin>>t; while(t--){ int n; int dp[110][110],a[110]; scanf("%d",&n); for(int i = 1; i <= n; ++i) {scanf("%d",&a[i]);dp[i][i] = 0;} for(int len = 2; len <= n; ++len){ for(int i = 1; i <= n-len+1; ++i){ int j = i+len-1; dp[i][j] = INF; for(int k = i+1; k < j; ++k){ dp[i][j] = MIN(dp[i][j],dp[i][k-1]+dp[k+1][j]+(len-1)*a[k]); } dp[i][j] = MIN(dp[i][j],dp[i][i]+dp[i+1][j]+(len-1)*a[i]); dp[i][j] = MIN(dp[i][j],dp[j][j]+dp[i][j-1]+(len-1)*a[j]); } } cout<<dp[1][n]<<endl; } return 0; } /* */