水题
#include <iostream> #include <cstring> #include <cstdio> #include <string> #define f first #define s second #define ll long long #define inf 1e17 using namespace std; pair<ll,ll> p[15]; int n,ct; ll dp[15][15]; int path[15][15]; ll DP(int x,int y){ if(dp[x][y]!=inf) return dp[x][y]; if(x==y) return dp[x][y]=0; if(x+1==y){ path[x][y]=x; return dp[x][y]=p[x].f*p[y].s*p[x].s; } ll ret=(ll)1e17; for(int i=x;i<y;i++){ ll now=DP(x,i)+DP(i+1,y)+p[x].f*p[y].s*p[i].s; if(now<ret){ ret=now; path[x][y]=i; } } return dp[x][y]=ret; } void solve(int x,int y){ if(x==y) {cout<<"A"<<ct++;return;} //if(path[x][y]==-1) return; cout<<"("; //if(path[x][y]==x&&x+1!=y) cout<<"A"<<ct++; solve(x,path[x][y]); //if(x+1==y) cout<<"A"<<ct++; cout<<" x "; //if(x+1==y) cout<<"A"<<ct++; solve(path[x][y]+1,y); //if(path[x][y]+1==y&&x+1!=y) cout<<"A"<<ct++; cout<<")"; } int main(){ //freopen("348","r",stdin); int cas=1; while(cin>>n&&n){ for(int i=0;i<n;i++) cin>>p[i].f>>p[i].s; for(int i=0;i<15;i++){ for(int j=0;j<15;j++){ dp[i][j]=(ll)1e17; } } memset(path,-1,sizeof path); DP(0,n-1); printf("Case %d: ",cas++); ct=1; solve(0,n-1); cout<<endl; } return 0; }