题意
n只狼排成一行，每次击败第i只狼需要ai bi-1 bi 1代价，击败后，相当于出列了，与i相邻两只狼成了相邻的。求击败所有狼的最小总代价。
分析
我开始一直以为是个环TAT。。
区间dp，dp[i][j]表示第i到第j只狼都被击败需要最少代价是多少。
dp[i][j]=dp[i][k-1] dp[k 1][j] b[i-1] b[j 1] a[k]
表示i到j只狼，最后击败的是第k只（i≤k≤j）。
从长度为1开始枚举，然后长度为2的...
l为长度，j=i l-1。
只要枚举最后击败的第k只，小区间的已经算出来，那大区间也就可以求出最小代价。
因为所有狼最后都要击败，可以把a[i]一开始就累加起来。
代码
代码语言：javascript复制#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
#define N 205
using namespace std;
int b[N];
ll dp[N][N];
int main()
{
int test;
scanf("%d",&test);
for(int t=1; t<=test; t )
{
int n;
scanf("%d",&n);
int a,s=0;
for(int i=0; i<n; i )
{
scanf("%d",&a);
s =a;
}
for(int i=1; i<=n; i ) scanf("%d",&b[i]);
memset(dp,0,sizeof dp);
for(int l=1; l<=n; l )
for(int i=1; i<=n-l 1; i )
{
int j=i l-1;
dp[i][j]=1e10;
for(int k=i; k<=j; k )
dp[i][j]=min(dp[i][j],dp[i][k-1] dp[k 1][j] b[i-1] b[j 1]);
}
dp[1][n] =s;
printf("Case #%d: %lldn",t,dp[1][n]);
}
return 0;
}
