http://acm.pku.edu.cn/JudgeOnline/problem?id=1695第一次做三位动态规划，看了谢迪的
《浅谈动态规划》，写出如下程序
#include "stdio.h"
int f[33][33][33];
int d[33][33];
int maxint=99999;
void main()
{
int T,i,j,k,n,opt;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(i=1;i<=n-1;i++) //读数据
for(j=i+1;j<=n;j++)
{
scanf("%d",&d[i][j]);
d[j][i]=d[i][j];
}
for(i=1;i<=n;i++)//初始化
for(j=1;j<=n;j++)
for(k=1;k<=n;k++)
f[i][j][k]=maxint;
f[1][1][1]=0;
for(k=2;k<=n;k++)
for(i=1;i<k;i++)
for(j=1;j<k;j++)
if(f[i][j][k-1]!=maxint)
{
if(f[i][j][k-1]+d[i][k]<f[j][k-1][k])
f[j][k-1][k]=f[i][j][k-1]+d[i][k];
if(f[i][j][k-1]+d[j][k]<f[i][k-1][k])
f[i][k-1][k]=f[i][j][k-1]+d[j][k];
if(f[i][j][k-1]+d[k-1][k]<f[i][k-1][k])
f[i][j][k]=f[i][j][k-1]+d[k-1][k];
}
opt=f[1][1][n];
for(i=1;i<n;i++)
for(j=1;j<n;j++)
if(f[i][j][n]<opt)opt=f[i][j][n];
printf("%d\n",opt);
}
}本地调试成功,不过提交上去总是wa,郁闷了我一个多小时了.
唉..
不过总算是自己做了一次三维动态规划了.希望哪个牛人可以告诉我这个程序哪里出问题了.