記憶化搜索，感覺題目中有矛盾，需要注意順序，還有輸出格式。
以下是我的代碼：
#include<stdio.h>
#include<string.h>
long d[21][21][21];
long w(long a,long b,long c)
{
if((a<=0||b<=0||c<=0)&&d[0][0][0]!=-1)
return d[0][0][0];
else if((a>20||b>20||c>20)&&d[20][20][20]!=-1)
return d[20][20][20];
else if(a>=0&&a<=20&&b>=0&&b<=20&&c>=0&&c<=20&&d[a][b][c]!=-1)
return d[a][b][c];
// 已經計算過 直接返回值
if(a<=0||b<=0||c<=0)
{
a=b=c=0;
d[a][b][c]=1;
}
else if(a>20||b>20||c>20)
{
a=b=c=20;
d[a][b][c]=w(20,20,20);
}
else if(a<b&&b<c)
d[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
else
d[a][b][c]=w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);
return d[a][b][c];
}
int main()
{
long a,b,c;
memset(d,-1,sizeof(d));// 未計算標記
scanf("%ld%ld%ld",&a,&b,&c);
while(a!=-1||b!=-1||c!=-1)
{
printf("w(%ld, %ld, %ld) = %ld\n",a,b,c,w(a,b,c));
scanf("%ld%ld%ld",&a,&b,&c);
}
return 0;
}
posted on 2010-01-06 19:37
lee1r 閱讀(231)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動態(tài)規(guī)劃