#include<stdio.h>
int s[2];
int l[7]={0};
int c[2][8]={{4,8,5,6,4,5,7,2},{2,7,9,3,4,8,4,3}};
int m[2][6]={{0,2,1,2,2,1},{0,2,3,1,3,4}};
int f[2][7]={0};
int fastway(int j,int i);
int fastway(int j,int i)
{
int a=0;
int b=0;
if(f[i][j]!=0)
return f[i][j];
if(j==1)
{
s[1]=c[1][j-1]+c[1][j];
s[0]=c[0][j-1]+c[0][j];
if(i==1)
return s[1];
if(i==0)
return s[0];
}
if(i==1)
{
//if(f[1][j]!=0)
// return f[1][j];
a=fastway((j-1),1)+c[1][j];
b=fastway((j-1),0)+m[0][j-1]+c[1][j];
if(a<b)
{
s[1]=a;
l[j-1]=1;
f[1][j]=a;
}
else
{
s[1]=b;
l[j-1]=0;
f[1][j]=b;
}
}
if(i==0)
{
//if(f[0][j]!=0)
// return f[0][j];
a = fastway((j-1),0)+c[0][j];
b = fastway((j-1),1)+m[1][j-1]+c[0][j];
if(a<b)
{
s[0]=a;
l[j-1]=0;
f[0][j]=a;
}
else
{
s[0]=b;
l[j-1]=1;
f[0][j]=b;
}
}
if(i==1)
return s[1];
if(i==0)
return s[0];
}
int main(int agc,char *agv[])
{
int i;
int j=7;
int temp1=fastway(6,0);
l[6]=0;
temp1=temp1+c[0][7];
for(i=1;i<j;i++)
printf("%d ",l[i]);
printf("%d\n",temp1);
int temp2=fastway(6,1);
temp2=temp2+c[1][7];
l[6]=1;
for(i=1;i<j;i++)
printf("%d ",l[i]);
printf("%d\n",temp2);
return 0;
}
|
