题目链接:
?pid=1331
?pid=1579
题目大意:
给一些递归条件,,给你三个数a、b、c,求出w(a,b,c)是多少。
思路:
按题目要求递归的话会超时,所以用dp[a][b][c]来保存下递归函数的值,自底向上得出结果。
AC代码:
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>using namespace std;int dp[30][30][30];int w(int a,int b,int c){if(a <=0 || b <=0 || c <= 0)return 1;if(a > 20 || b > 20 || c > 20)return w(20,20,20);if(dp[a][b][c])return dp[a][b][c];if(a < b && b < c)return dp[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) – w(a, b-1, c);return dp[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);}int main(){int a,b,c;while(~scanf("%d%d%d",&a,&b,&c)){if(a == -1 && b == -1 && c == -1)break;memset(dp,0,sizeof(dp));printf("w(%d, %d, %d) = %d\n",a,b,c,w(a,b,c));}return 0;}
谁的指间滑过了千年时光;谁在反反复复中追问可曾遗忘;