HDU 5151 Dire Wolf

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
const int inf=1000000000;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
    return x*f;
}
int n,a[205],f[205][205];
int main()
{
    int T=read();
    for(int kase=1;kase<=T;kase++)
    {
        n=read();
        int ans=0;
        for(int i=1;i<=n;i++)ans+=read();
        for(int i=1;i<=n;i++)a[i]=read();
        a[n+1]=0;
        for(int i=1;i<=n;i++)f[i][i]=a[i-1]+a[i+1];
        for(int len=2;len<=n;len++)
          for(int i=1;i+len-1<=n;i++)
          {
              int j=i+len-1;
              f[i][j]=inf;
              for(int h=i;h<=j;h++)
                f[i][j]=min(f[i][j],f[i][h-1]+f[h+1][j]+a[i-1]+a[j+1]);
          }
        printf("Case #%d: %d\n",kase,ans+f[1][n]);
    }
    return 0;
}