題目的意思就是：給出一個(gè)無向圖，給定起點(diǎn)，給定終點(diǎn)，給定消耗，走法基本不受限制，問需要有多少種方法從起點(diǎn)回到終點(diǎn)。
一開始看到這一題感覺是很簡單的動(dòng)態(tài)規(guī)劃，可惜不小心把高精度給寫錯(cuò)了，結(jié)果一分未得。高精度寫錯(cuò)的原因是為了提高效率寫了一個(gè)高精度給高精度賦值的函數(shù)，賦值時(shí)沒有初始化。后來改為直接賦值就AC了。
定義狀態(tài)d[i][j]表示消耗i從起點(diǎn)到j結(jié)點(diǎn)可以的走法，則狀態(tài)轉(zhuǎn)移方程如下：
d[i][j]=sum{d[i-cost[k][j]][k]}，其中k表示和j相連的結(jié)點(diǎn)。
邊界是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 閱讀(133)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動(dòng)態(tài)規(guī)劃