AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

AcWing 271. 杨老师的照相排列    原题链接    中等

作者: 作者的头像   落日的悲伤 ,  2019-09-13 13:21:37 ,  所有人可见 ,  阅读 1795


8


1

记忆化搜索,没有不必要的循环,代码简单易懂。

#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;
}

0 评论

App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息