http://acm.pku.edu.cn/JudgeOnline/problem?id=1695第一次做三位動(dòng)態(tài)規(guī)劃，看了謝迪的
《淺談動(dòng)態(tài)規(guī)劃》，寫出如下程序
#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++) //讀數(shù)據(jù)
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);
}
}本地調(diào)試成功,不過提交上去總是wa,郁悶了我一個(gè)多小時(shí)了.
唉..
不過總算是自己做了一次三維動(dòng)態(tài)規(guī)劃了.希望哪個(gè)牛人可以告訴我這個(gè)程序哪里出問題了.