题意:
有n个地方,每两个点之间需要的时间已知,现在有3辆车在地点1,要把杂志送到2,3...n,同一时刻只能有一辆车在走,且送到i之前必须送到i-1,求完成任务需要的最少时间。
分析:
dp[a][[b][c]表示三辆车由近到远在a,b,c三个地方所要的最少时间。当n==6时,2,2,1,3,1,3。3,3,1,2,1,2。2,2,1,1,1,3这些访问序列都能被dp[2][5][6]表示,动态规划能避免访问状态空间中很多多余状态。
代码:
//poj 1695
//sep9
#include <iostream>
using namespace std;
int n;
int dp[32][32][32];
int t[32][32];int search(int a,int b,int c)
{if(dp[a][b][c]!=-1)return dp[a][b][c]; int ans=INT_MAX;if(b==c-1){for(int i=1;i<=c-1;++i){int x=min(min(i,a),min(i,b));int z=max(max(i,a),max(i,b));int y=i+a+b-x-z;ans=min(ans,search(x,y,z)+t[i][c]);}}int i=c-1;int x=min(min(i,a),min(i,b));int z=max(max(i,a),max(i,b));int y=a+b+i-x-z;ans=min(ans,search(x,y,z)+t[i][c]);return dp[a][b][c]=ans;
}int main()
{int cases;scanf("%d",&cases);while(cases--){scanf("%d",&n);for(int i=1;i<n;++i)for(int j=i+1;j<=n;++j)scanf("%d",&t[i][j]); memset(dp,-1,sizeof(dp));int ans=INT_MAX;dp[1][1][1]=0;for(int i=1;i<=n;++i)for(int j=i;j<=n;++j)ans=min(ans,search(i,j,n));printf("%d\n",ans);}return 0;
}