题目的意思就是：给出一个无向图，给定起点，给定终点，给定消耗，走法基本不受限制，问需要有多少种方法从起点回到终点。
一开始看到这一题感觉是很简单的动态规划，可惜不小心把高精度给写错了，结果一分未得。高精度写错的原因是为了提高效率写了一个高精度给高精度赋值的函数，赋值时没有初始化。后来改为直接赋值就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 阅读(112)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：动态规划