[JSOI2010 Express Service 快递服务]动态规划

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1820
【算法分析】
假如用F[i][j][k][l]表示第i个要求，三个货车司机分别在j，k，l三个点时的最小费用。
那么转移就非常简单。
然后可以发现，j，k，l中总有一个是等于Q[i]的。于是删掉这维，滚动数组dp即可。
【CODE】
#include #include #include const int N=205;
int n,q;
int d[N][N],List[88888];
int F[2][N][N];

int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
scanf("%d",&d[i][j]);
for (int i=1;i<=n;i++) d[i][i]=0;
memset(F,50,sizeof(F));
List[0]=1; F[0][2][3]=F[0][3][2]=0;
q=1;
int p=1;
while (scanf("%d",&List[q])!=EOF){
memset(F[p],50,sizeof(F[p]));
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++){
F[p][i][j] F[p][List[q-1]][j] F[p][List[q-1]][i] }
q++;
p=1-p;
}
int ans=0x7FFFFFFF;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
ans printf("%dn",ans);
}