[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過了。
經典的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;
}
留言
張貼留言