讨论 / 求大牛指导这道DP
帐号 2011-10-03 21:48:00
点我顶贴 收藏 删除
#include<stdio.h>

#define int_m 2000000000

int bw[1001][17][17][17],array_a[1001],array_b[1001],f[17][17],n;

int min(int a,int b)

{

if(a>b)

return b;

return a;

}

void cal()

{

int ans,tt,i,j,k;

ans=int_m;

for(tt=1;tt<=n;tt++)

for(i=1;i<=16;i++)

for(j=1;j<=16;j++)

for(k=1;k<=16;k++)

bw[n][i][j][k]=int_m;

bw[0][array_b[1]][1][1]=0;

bw[0][1][array_b[1]][1]=0;

bw[0][1][1][array_b[1]]=0;

for(tt=2;tt<=n;tt++)

{

for(i=1;i<=16;i++)

for(j=1;j<=16;j++)

{

bw[tt][array_b[tt]][j][array_b[tt-1]]=min(bw[tt][array_b[tt]][j][array_b[tt-1]],bw[tt-1][i][j][array_b[tt-1]]+f[i][array_b[tt]]);

bw[tt][i][array_b[tt]][array_b[tt-1]]=min(bw[tt][i][array_b[tt]][array_b[tt-1]],bw[tt-1][i][j][array_b[tt-1]]+f[j][array_b[tt]]);

bw[tt][i][j][array_b[tt]]=min(bw[tt][i][j][array_b[tt]],bw[tt-1][i][j][array_b[tt-1]]+f[array_b[tt-1]][array_b[tt]]);

bw[tt][array_b[tt]][array_b[tt-1]][j]=min(bw[tt][array_b[tt]][array_b[tt-1]][j],bw[tt-1][i][array_b[tt-1]][j]+f[i][array_b[tt]]);

bw[tt][i][array_b[tt-1]][array_b[tt]]=min(bw[tt][i][array_b[tt-1]][array_b[tt]],bw[tt-1][i][array_b[tt-1]][j]+f[j][array_b[tt]]);

bw[tt][i][array_b[tt]][j]=min(bw[tt][i][array_b[tt]][j],bw[tt-1][i][array_b[tt-1]][j]+f[array_b[tt-1]][array_b[tt]]);

bw[tt][array_b[tt-1]][array_b[tt]][j]=min(bw[tt][array_b[tt-1]][array_b[tt]][j],bw[tt-1][array_b[tt-1]][i][j]+f[i][array_b[tt]]);

bw[tt][array_b[tt-1]][i][array_b[tt]]=min(bw[tt][array_b[tt-1]][i][array_b[tt]],bw[tt-1][array_b[tt-1]][i][j]+f[j][array_b[tt]]);

bw[tt][array_b[tt]][i][j]=min(bw[tt][array_b[tt]][i][j],bw[tt-1][array_b[tt-1]][i][j]+f[array_b[tt-1]][array_b[tt]]);

}

}

for(i=1;i<=16;i++)

for(j=1;j<=16;j++)

for(k=1;k<=16;k++)

if(bw[n][i][j][k]<ans)

ans=bw[n][i][j][k];

printf("%d\n",ans);

}

void qsort(int l,int r)

{

if(l>=r)

return ;

int i=l,j=r-1,k,s1,s2;

k=r;

s1=array_a[r];

s2=array_b[r];

while(i<j)

{

for(;i<=j;i++)

if(array_a[i]>s1)

{

array_a[k]=array_a[i];

array_b[k]=array_b[i];

k=i;

break;

}

for(;j>i;j--)

if(array_a[j]<s1)

{

array_a[k]=array_a[j];

array_b[k]=array_b[j];

k=j;

break;

}

}

array_a[k]=s1;

array_b[k]=s2;

qsort(l,k-1);

qsort(k+1,r);

}

void getn()

{

int t,i,j,k;

scanf("%d",&t);

for(i=1;i<=t;i++)

{

scanf("%d",&n);

for(j=1;j<=n;j++)

scanf("%d%d",&array_a[j],&array_b[j]);

for(j=1;j<=16;j++)

for(k=1;k<=16;k++)

scanf("%d",&f[j][k]);

qsort(1,n);

cal();

}

}

int main()

{

getn();

return 0;

}

我的程序放上去无输出。这是为什么?

我无奈了。

#1 lx99410@2011-10-03 21:48:00
回复 删除
回复 楼主帐号 的帖子

仔细看题目!!!

引用“接下来有三组格式相同的输入,都是一个16*16的矩阵,表示三根手指中的某根手指从i格子移动到j格子需要F[i][j]的体力。输入保证F[i][j]=F[j][i],并且F[i][i]=0。矩阵中所有元素小于500。”

查看更多回复
提交回复