Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //UVa Q348
- #include <bits/stdc++.h>
- using namespace std;
- int dp[11][11];
- int trans[11][11];
- int arr[11];
- string ans;
- void getans(int l, int r){
- if(l == r){
- ans += "A";
- if(l == 9)ans += "10";
- else ans += (char)(l+'1');
- return;
- }
- ans += "(";
- getans(l, trans[l][r]);
- ans += " x ";
- getans(trans[l][r]+1, r);
- ans += ")";
- }
- int32_t main(){
- int n;
- int cnt = 0;
- while(cin >> n){
- if(n == 0)break;
- for(int i = 0; i <= n; ++i)
- for(int j = 0; j <= n; ++j)
- if(i != j)dp[i][j] = INT_MAX;
- for(int i = 0; i < n; ++i)cin >> arr[i] >> arr[i+1];
- for(int l = 1; l < n; ++l){
- for(int i = 0; i+l < n; ++i){
- int j = i+l;
- for(int k = i; k < j; ++k){
- if(dp[i][j] > dp[i][k] + dp[k+1][j] + arr[i]*arr[k+1]*arr[j+1]){
- dp[i][j] = dp[i][k] + dp[k+1][j] + arr[i]*arr[k+1]*arr[j+1];
- trans[i][j] = k;
- }
- }
- //cout << i << ' ' << j << ' ' << dp[i][j] << '\n';
- }
- }
- getans(0, n-1);
- cout << "Case " << ++cnt << ": " << ans << '\n';
- ans = "";
- }
- return 0;
- }
RAW Paste Data