记忆化搜索,没有不必要的循环,代码简单易懂。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[31][31][31][31][31]={0};
ll dfs(int a,int b,int c,int d,int e){
ll &ans=dp[a][b][c][d][e];
if(ans)
return ans;
// cout << a << b << c << d << e << endl;
if(a-1>=b && a-1>=0)
ans+=dfs(a-1,b,c,d,e);
if(b-1>=c && b-1>=0)
ans+=dfs(a,b-1,c,d,e);
if(c-1>=d && c-1>=0)
ans+=dfs(a,b,c-1,d,e);
if(d-1>=e && d-1>=0)
ans+=dfs(a,b,c,d-1,e);
if(e-1>=0)
ans+=dfs(a,b,c,d,e-1);
return ans;
}
int main()
{
int n;
dp[1][0][0][0][0]=1;
while(cin >> n && n){
int a=0,b=0,c=0,d=0,e=0;
if(n==1)
cin >> a;
else if(n==2)
cin >> a >> b;
else if(n==3)
cin >> a >> b >> c;
else if(n==4)
cin >> a >> b >> c >> d;
else
cin >> a >> b >> c >> d >> e;
cout << dfs(a,b,c,d,e) << endl;
}
return 0;
}