Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

哪位大牛帮我看看，我用的是分阶段的DP，没有用三维DP

Posted by 20061000999 at 2008-08-09 14:42:39 on Problem 1695
```#include"stdio.h"
#define INF 0x7fffffff
typedef struct
{
int car[3];
int total;
}state;
int main()
{
int i,j,k,n,m,time[31][31],t,s;
state f[35][3];

scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
scanf("%d",&time[i][j]);

f[0][0].total=0;f[0][1].total=0;f[0][2].total=0;
f[1][0].total=time[0][1];f[1][1].total=time[0][1];f[1][2].total=time[0][1];
f[1][0].car[0]=1;f[1][0].car[1]=0;f[1][0].car[2]=0;
f[1][1].car[0]=0;f[1][1].car[1]=1;f[1][1].car[2]=0;
f[1][2].car[0]=0;f[1][2].car[1]=0;f[1][2].car[2]=1;
for(i=2;i<n;i++)
for(j=0;j<3;j++)
{
for(k=0,s=INF;k<3;k++)
if(f[i-1][k].total+time[f[i-1][k].car[j]][i]<s)
{
s=f[i-1][k].total+time[f[i-1][k].car[j]][i];
m=k;
}
f[i][j].car[0]=f[i-1][m].car[0];
f[i][j].car[1]=f[i-1][m].car[1];
f[i][j].car[2]=f[i-1][m].car[2];
f[i][j].car[j]=i;
f[i][j].total=s;
}

for(i=0,s=INF;i<3;i++)
if(s>f[n-1][i].total)s=f[n-1][i].total;

printf("%d\n",s);
}
return 1;
}```

Followed by: