1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 using namespace std; 5 const int N = 200 + 5; 6 const int inf = 0x3f3f3f3f; 7  8 int n; 9 int a[N],b[N];10 int dp[N][N];11 12 int main()13 {14     int T;scanf("%d",&T);15     for(int kase=1;kase<=T;kase++)16     {17         scanf("%d",&n);18         memset(a,0,sizeof(a));19         memset(b,0,sizeof(b));20         for(int i=1;i<=n;i++) scanf("%d",a+i);21         for(int i=1;i<=n;i++) scanf("%d",b+i);22         23         memset(dp,inf,sizeof(dp));24         for(int len=0;len<=n;len++)25         {26             for(int i=1;i+len<=n;i++)27             {28                 int j = i + len;29                 for(int k=i;k<=j;k++)30                 {31                     dp[i][j] = min(dp[i][j],b[i-1]+b[j+1]+a[k]+(k>i?dp[i][k-1]:0)+(k<j?dp[k+1][j]:0));32                 }33             }34         }35         printf("Case #%d: %d\n",kase,dp[1][n]);36     }37 }