SP15637 Mr Youngs Picture Permutations 高维动态规划

问题描述

LG-SP

题解

发现\(n,k\)都非常小，尤其是\(k,k\le 5\)，于是直接开\(5\)维进行\(\mathrm{DP}\)

用记忆化搜索实现。

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;

#define int long long

template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-'){
        fh=-1;ch=getchar();
    }
    else fh=1;
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    x*=fh;
}

int opt[31][31][31][31][31];
int a[7],n;

int dp(int a,int b,int c,int d,int e){
    if(!a&&!b&&!c&&!d&&!e) return opt[a][b][c][d][e]=1;
    int &k=opt[a][b][c][d][e];
    if(k) return k;
    if(a>b) k+=dp(a-1,b,c,d,e);
    if(b>c) k+=dp(a,b-1,c,d,e);
    if(c>d) k+=dp(a,b,c-1,d,e);
    if(d>e) k+=dp(a,b,c,d-1,e);
    if(e>0) k+=dp(a,b,c,d,e-1);
    return k;
}

signed main(){
    while(1){
        read(n);
        memset(opt,0,sizeof(opt));
        if(!n) return 0;
        for(int i=1;i<=n;i++) read(a[i]);
        for(int i=n+1;i<=5;i++) a[i]=0;
        printf("%lld\n",dp(a[1],a[2],a[3],a[4],a[5]));
    }
    return 0;
}