原题链接

题目大意

国王要攻打其他的国家，要攻打的国家在地图上排成一行。每一个国家有一个$cost$值，如果国王准备攻打第i个国家，那么便需要向该国家左右两边连着的且未被攻打的每个国家缴纳$cost_i$个金币，问国王按什么顺序打这$n$个国家才能使缴纳的金币最少。

解题思路

思路就是这道题目的标题。
首先考虑只有一个国家的情况下，需要付出的金币数$w=0$;
当有两个国家的情况下，最好的情况应该是攻打$cost$值较小的国家，付给另一个国家钱，然后攻打$cost$值较大的国家时的花费是0，$w=min(cost_1,cost_2)$;
当有三个国家的情况下，$w=第一个攻打的国家的cost值*2+攻打剩下两个国家的最小花费$，我们可以依次尝试第一个要攻打的国家，第一次攻打后，未被攻打的国家就被分为了两个区间，我们只需要知道这攻打这两个区间内国家的最小花费分别是多少就能得出攻打三个国家的最小花费，而这两个区间的长度必定小于三，我们可以先把结果处理出来
同理有四个国家的情况下，我们可以枚举第一个攻打的国家，再加上攻打分成的两个区间国家的最小花费来得出。
依此类推，一直到n个国家。
令dp[i][j]代表攻打区间$[i,j](i<=j)$内所有国家的最小花费
$$dp[i][j] = min(cost[k]*(j-i)+dp[i][k-1]+dp[k+1][j]) k\in [i,j]$$
最后输出$dp[1][n]$即可

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 105;

ll cost[maxn];
ll dp[maxn][maxn];

ll cal_cost(int l,int r)
{
	ll d = INT_MAX;
	int num = r-l;
	for(int i=l;i<=r;++i)
	{
		d = min(d,dp[l][i-1]+dp[i+1][r]+cost[i]*num);
	}
	return d;
}

void cal_dp(int n)
{
	for(int i=3;i<=n;i++)
	{
		for(int l=1,r=l+i-1;r<=n;l++,r++)
		{
			dp[l][r] = cal_cost(l,r);
		}
	}
}



int T;
void init(int n)
{
	for(int i=1;i<=n;++i)
	{
		cost[i]=0;
		for(int j=1;j<=n;++j)
		{
			dp[i][j]=0;
		}
	}
}
int main()
{
	cin>>T;
	while(T--)
	{
		int n;
		cin>>n;
		init(n);
		for(int i=1;i<=n;++i)
		{
			cin>>cost[i];			
			dp[i][i]=0;
			dp[i-1][i]=min(cost[i],cost[i-1]);
		}
		cal_dp(n);
		
		cout<<dp[1][n]<<endl;
		
	} 
}