[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;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology