題目的意思就是：給出一個無向圖，給定起點，給定終點，給定消耗，走法基本不受限制，問需要有多少種方法從起點回到終點。
一開始看到這一題感覺是很簡單的動態規劃，可惜不小心把高精度給寫錯了，結果一分未得。高精度寫錯的原因是為了提高效率寫了一個高精度給高精度賦值的函數，賦值時沒有初始化。后來改為直接賦值就AC了。
定義狀態d[i][j]表示消耗i從起點到j結點可以的走法，則狀態轉移方程如下：
d[i][j]=sum{d[i-cost[k][j]][k]}，其中k表示和j相連的結點。
邊界是d[0][0]=1。
以下是我的代碼：
#include<stdio.h>
#define MAXINT 2000000000
typedef struct
{
long len,s[51];
}high;
long N,L,g[55][55];
high d[601][51];
void add(high *a,high *b,high *c)
{
long i,l=(a->len>b->len?a->len:b->len);
for(i=0;i<=50;i++)
c->s[i]=0;
for(i=0;i<l;i++)
{
c->s[i]+=(a->s[i]+b->s[i]);
if(c->s[i]>=10000)
{
c->s[i+1]+=c->s[i]/10000;
c->s[i]%=10000;
}
}
c->len=l;
if(c->s[c->len]!=0)
c->len++;
}
void init()
{
long i,j,w;
scanf("%ld%ld",&N,&L);
for(i=0;i<=N;i++)
for(j=0;j<=N;j++)
g[i][j]=MAXINT;
for(i=1;i<=N;i++)
{
scanf("%ld",&w);
if(i<N)
g[i][i+1]=g[i+1][i]=w;
else if(i==N)
g[i][1]=g[1][i]=w;
}
for(i=1;i<=N;i++)
{
scanf("%ld",&w);
g[0][i]=w;
g[i][0]=w;
}
}
void work()
{
long i,j,k;
high zero={1,{0}},one={1,{1}};
high tmp=zero;
for(i=0;i<=L;i++)
for(j=0;j<=N;j++)
d[i][j]=zero;
// Clear
d[0][0]=one;
for(k=1;k<=L;k++)
for(i=0;i<=N;i++)
for(j=0;j<=N;j++)
if(g[i][j]!=MAXINT&&k-g[i][j]>=0)
{
tmp=d[k][i];
add(&tmp,&d[k-g[i][j]][j],&d[k][i]);
}
}
void write()
{
long i,l;
l=d[L][0].len;
printf("%ld",d[L][0].s[l-1]);
for(i=l-2;i>=0;i--)
{
if(d[L][0].s[i]<1000) printf("%ld",0);
if(d[L][0].s[i]<100) printf("%ld",0);
if(d[L][0].s[i]<10) printf("%ld",0);
printf("%ld",d[L][0].s[i]);
}
}
int main()
{
init();
work();
write();
// getchar();getchar();
return 0;
}
posted on 2010-01-06 19:53
lee1r 閱讀(130)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動態規劃