[TIOJ] 1488. D.正直DE

題目連結:http://tioj.infor.org/problems/1488

---

經典的DP題，狀態$dp[i][j]$是將矩陣$[i,j]$乘起來所需的最小值，稍微想一下後就會發現轉移就是$ dp[i][j] = \min_{ \forall i \leq k < j }dp[i][k]+dp[k+1][j] + M_i[0] \times M_k[1] \times M_j[1] $($M_x[i]$)為矩陣$x$的第$i$維。
不過在DP有個麻煩的點就是他的順序，因為要是沒有好的順序就會算出不對的答案，一個解決方法是直接top-down，但是常數會變大，這題又卡的有點緊，可能會TLE。這時其實發現迴圈的第一維枚舉右界，第二維再倒過來求左界，他長度就會是遞增而且前面都已經DP過了。

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
typedef pair<int,int> PII;
#define FF first
#define SS second

const int N = 1000 + 5;
const lld INF = 1LL<<60;
PII mtx[N];
lld dp[5][N][N];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int T; cin>>T;
	lld sm=0;
	for(int t=0;t<T;++t){
		int n;cin>>n;
		for(int i=0;i<n;++i) cin>>mtx[i].FF>>mtx[i].SS;
		fill(dp[t][0], dp[t][n]+n, INF);
		for(int i=0;i<n;++i) dp[t][i][i] = 0;
		for(int j=0;j<n;++j){
			for(int i=j-1;i>=0;--i){
				for(int k=i;k<j;++k){
					dp[t][i][j]=min(dp[t][i][j], \
						dp[t][i][k]+dp[t][k+1][j] + mtx[i].FF*mtx[k].SS*mtx[j].SS);
				}
			}
		}
		cout<<(lld)ceil(dp[t][0][n-1]/1000.)<<'\n';
		sm+=dp[t][0][n-1];
	}
	cout<<(lld)ceil(sm/1000.)<<'\n';
	return 0;
}