题意：有个人去一幢楼送礼物，他用两根柱状的容器装礼物，每次只能从容器的两端取出礼物送出去，上一层楼花费5的体力，下一层楼花费3的体力。求送完所有礼物耗费的最少体力。
分析：不难的题目，只是目前写的人比较少而已。状态表示还是很好想出来的。
dp[i1][j1][i2][j2][0]--第一根柱子到两端为i1,j1都送完,第二根到两端为i2,j2都送完，最后送的是a[i1]这个礼物所花费的最小体力。
dp[i1][j1][i2][j2][1]--第一根柱子到两端为i1,j1都送完,第二根到两端为i2,j2都送完，最后送的是a[j1]这个礼物所花费的最小体力。
dp[i1][j1][i2][j2][2]--第一根柱子到两端为i1,j1都送完,第二根到两端为i2,j2都送完，最后送的是b[i2]这个礼物所花费的最小体力。
dp[i1][j1][i2][j2][3]--第一根柱子到两端为i1,j1都送完,第二根到两端为i2,j2都送完，最后送的是b[j2]这个礼物所花费的最小体力。
这样的话，转移就很明显了，每种状态都有可能由4种状态转移过来，具体转移看代码。
如果方程的最后一维表示的是最后停在哪一层的话，就不行了，30*30*30*30*100的空间肯定是开不了的，所以用最后一维表示最后送出的礼物是哪一个，时空复杂度都降低了。
#include <iostream>
#include <stdio.h>
#include <memory.h>
using namespace std;
#define inf 2000000000
int dp[32][32][32][32][4],n,m,a[32],b[32];
int main()
{
int t,i,j,i1,j1,i2,j2,ans,cost,zt;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d",a+i);
scanf("%d",&m);
for(i=1;i<=m;i++) scanf("%d",b+i);
a[0]=1; a[n+1]=1; b[0]=1; b[m+1]=1; // 这里设置这些虚拟的楼层是为了方便设置边界
memset(dp,-1,sizeof(dp));
dp[0][n+1][0][m+1][0]=0; // 初始化
dp[0][n+1][0][m+1][1]=0;
dp[0][n+1][0][m+1][2]=0;
dp[0][n+1][0][m+1][3]=0;
for(i1=0;i1<=n;i1++)
{
for(j1=n+1;j1>i1;j1--)
{
for(i2=0;i2<=m;i2++)
{
for(j2=m+1;j2>i2;j2--) // 下面就是转移过程了
{
if(i1>0&&dp[i1-1][j1][i2][j2][0]!=-1)
{
if(a[i1]>a[i1-1]) cost=(a[i1]-a[i1-1])*5;
else cost=(a[i1-1]-a[i1])*3;
if(dp[i1-1][j1][i2][j2][0]+cost<dp[i1][j1][i2][j2][0]||dp[i1][j1][i2][j2][0]==-1)
dp[i1][j1][i2][j2][0]=dp[i1-1][j1][i2][j2][0]+cost;
}
if(i1>0&&dp[i1-1][j1][i2][j2][1]!=-1)
{
if(a[i1]>a[j1]) cost=(a[i1]-a[j1])*5;
else cost=(a[j1]-a[i1])*3;
if(dp[i1-1][j1][i2][j2][1]+cost<dp[i1][j1][i2][j2][0]||dp[i1][j1][i2][j2][0]==-1)
dp[i1][j1][i2][j2][0]=dp[i1-1][j1][i2][j2][1]+cost;
}
if(i1>0&&dp[i1-1][j1][i2][j2][2]!=-1)
{
if(a[i1]>b[i2]) cost=(a[i1]-b[i2])*5;
else cost=(b[i2]-a[i1])*3;
if(dp[i1-1][j1][i2][j2][2]+cost<dp[i1][j1][i2][j2][0]||dp[i1][j1][i2][j2][0]==-1)
dp[i1][j1][i2][j2][0]=dp[i1-1][j1][i2][j2][2]+cost;
}
if(i1>0&&dp[i1-1][j1][i2][j2][3]!=-1)
{
if(a[i1]>b[j2]) cost=(a[i1]-b[j2])*5;
else cost=(b[j2]-a[i1])*3;
if(dp[i1-1][j1][i2][j2][3]+cost<dp[i1][j1][i2][j2][0]||dp[i1][j1][i2][j2][0]==-1)
dp[i1][j1][i2][j2][0]=dp[i1-1][j1][i2][j2][3]+cost;
}
/**//*--------------------------------------------------------------------------------------------------------*/
if(j1<n+1&&dp[i1][j1+1][i2][j2][0]!=-1)
{
if(a[j1]>a[i1]) cost=(a[j1]-a[i1])*5;
else cost=(a[i1]-a[j1])*3;
if(dp[i1][j1+1][i2][j2][0]+cost<dp[i1][j1][i2][j2][1]||dp[i1][j1][i2][j2][1]==-1)
dp[i1][j1][i2][j2][1]=dp[i1][j1+1][i2][j2][0]+cost;
}
if(j1<n+1&&dp[i1][j1+1][i2][j2][1]!=-1)
{
if(a[j1]>a[j1+1]) cost=(a[j1]-a[j1+1])*5;
else cost=(a[j1+1]-a[j1])*3;
if(dp[i1][j1+1][i2][j2][1]+cost<dp[i1][j1][i2][j2][1]||dp[i1][j1][i2][j2][1]==-1)
dp[i1][j1][i2][j2][1]=dp[i1][j1+1][i2][j2][1]+cost;
}
if(j1<n+1&&dp[i1][j1+1][i2][j2][2]!=-1)
{
if(a[j1]>b[i2]) cost=(a[j1]-b[i2])*5;
else cost=(b[i2]-a[j1])*3;
if(dp[i1][j1+1][i2][j2][2]+cost<dp[i1][j1][i2][j2][1]||dp[i1][j1][i2][j2][1]==-1)
dp[i1][j1][i2][j2][1]=dp[i1][j1+1][i2][j2][2]+cost;
}
if(j1<n+1&&dp[i1][j1+1][i2][j2][3]!=-1)
{
if(a[j1]>b[j2]) cost=(a[j1]-b[j2])*5;
else cost=(b[j2]-a[j1])*3;
if(dp[i1][j1+1][i2][j2][3]+cost<dp[i1][j1][i2][j2][1]||dp[i1][j1][i2][j2][1]==-1)
dp[i1][j1][i2][j2][1]=dp[i1][j1+1][i2][j2][3]+cost;
}
/**//*--------------------------------------------------------------------------------------------------------*/
if(i2>0&&dp[i1][j1][i2-1][j2][0]!=-1)
{
if(b[i2]>a[i1]) cost=(b[i2]-a[i1])*5;
else cost=(a[i1]-b[i2])*3;
if(dp[i1][j1][i2-1][j2][0]+cost<dp[i1][j1][i2][j2][2]||dp[i1][j1][i2][j2][2]==-1)
dp[i1][j1][i2][j2][2]=dp[i1][j1][i2-1][j2][0]+cost;
}
if(i2>0&&dp[i1][j1][i2-1][j2][1]!=-1)
{
if(b[i2]>a[j1]) cost=(b[i2]-a[j1])*5;
else cost=(a[j1]-b[i2])*3;
if(dp[i1][j1][i2-1][j2][1]+cost<dp[i1][j1][i2][j2][2]||dp[i1][j1][i2][j2][2]==-1)
dp[i1][j1][i2][j2][2]=dp[i1][j1][i2-1][j2][1]+cost;
}
if(i2>0&&dp[i1][j1][i2-1][j2][2]!=-1)
{
if(b[i2]>b[i2-1]) cost=(b[i2]-b[i2-1])*5;
else cost=(b[i2-1]-b[i2])*3;
if(dp[i1][j1][i2-1][j2][2]+cost<dp[i1][j1][i2][j2][2]||dp[i1][j1][i2][j2][2]==-1)
dp[i1][j1][i2][j2][2]=dp[i1][j1][i2-1][j2][2]+cost;
}
if(i2>0&&dp[i1][j1][i2-1][j2][3]!=-1)
{
if(b[i2]>b[j2]) cost=(b[i2]-b[j2])*5;
else cost=(b[j2]-b[i2])*3;
if(dp[i1][j1][i2-1][j2][3]+cost<dp[i1][j1][i2][j2][2]||dp[i1][j1][i2][j2][2]==-1)
dp[i1][j1][i2][j2][2]=dp[i1][j1][i2-1][j2][3]+cost;
}
/**//*--------------------------------------------------------------------------------------------------------*/
if(j2<m+1&&dp[i1][j1][i2][j2+1][0]!=-1)
{
if(b[j2]>a[i1]) cost=(b[j2]-a[i1])*5;
else cost=(a[i1]-b[j2])*3;
if(dp[i1][j1][i2][j2+1][0]+cost<dp[i1][j1][i2][j2][3]||dp[i1][j1][i2][j2][3]==-1)
dp[i1][j1][i2][j2][3]=dp[i1][j1][i2][j2+1][0]+cost;
}
if(j2<m+1&&dp[i1][j1][i2][j2+1][1]!=-1)
{
if(b[j2]>a[j1]) cost=(b[j2]-a[j1])*5;
else cost=(a[j1]-b[j2])*3;
if(dp[i1][j1][i2][j2+1][1]+cost<dp[i1][j1][i2][j2][3]||dp[i1][j1][i2][j2][3]==-1)
dp[i1][j1][i2][j2][3]=dp[i1][j1][i2][j2+1][1]+cost;
}
if(j2<m+1&&dp[i1][j1][i2][j2+1][2]!=-1)
{
if(b[j2]>b[i2]) cost=(b[j2]-b[i2])*5;
else cost=(b[i2]-b[j2])*3;
if(dp[i1][j1][i2][j2+1][2]+cost<dp[i1][j1][i2][j2][3]||dp[i1][j1][i2][j2][3]==-1)
dp[i1][j1][i2][j2][3]=dp[i1][j1][i2][j2+1][2]+cost;
}
if(j2<m+1&&dp[i1][j1][i2][j2+1][3]!=-1)
{
if(b[j2]>b[j2+1]) cost=(b[j2]-b[j2+1])*5;
else cost=(b[j2+1]-b[j2])*3;
if(dp[i1][j1][i2][j2+1][3]+cost<dp[i1][j1][i2][j2][3]||dp[i1][j1][i2][j2][3]==-1)
dp[i1][j1][i2][j2][3]=dp[i1][j1][i2][j2+1][3]+cost;
}
/**//*--------------------------------------------------------------------------------------------------------*/
}
}
}
}
ans=inf;
for(i=0;i<=n;i++)
{
for(j=0;j<=m;j++)
{
for(zt=0;zt<4;zt++)
{
if(dp[i][i+1][j][j+1][zt]!=-1&&dp[i][i+1][j][j+1][zt]<ans)
ans=dp[i][i+1][j][j+1][zt];
}
}
}
printf("%d\n",ans);
}
return 0;
}