【题解】POJ2279 Mr.Young′s Picture Permutations dp

佚名 6年前 (2019-05-14) 随笔 1771人围观抢沙发百度已收录

【题解】POJ2279 Mr.Young′s Picture Permutations dp

钦定从小往大放，然后直接dp。

\(dp(t1,t2,t3,t4,t5)\)代表每一行多少人，判断边界就能dp。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

然后你发现\(30^5\)开不下，但是你仔细观察由于它保证\(\sum < 30\)所以你只用开\(30^5 \div 5!\)就好了。

具体为什么我相信你会

//@winlere
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;  typedef long long ll;

const int maxn=35;
unsigned int dp[maxn][maxn/2+1][maxn/3+1][maxn/4+1][maxn/5+1];
int l[7];


int main(){
      int n;
      while(cin>>n,n){
        memset(dp,0,sizeof dp);
        memset(l,0,sizeof l);
        for(register int t=1;t<=n;++t)
          cin>>l[t];
        dp[0][0][0][0][0]=1;
        for(register int t1=1;t1<=l[1];++t1){
          for(register int t2=0;t2<=min(l[2],t1);++t2){
            for(register int t3=0;t3<=min(l[3],t2);++t3){
                  for(register int t4=0;t4<=min(l[4],t3);++t4){
                    for(register int t5=0;t5<=min(l[5],t4);++t5){\

                      unsigned int&k=dp[t1][t2][t3][t4][t5];
                      if(t5)k+=dp[t1][t2][t3][t4][t5-1];
                      if(t4-1>=t5)k+=dp[t1][t2][t3][t4-1][t5];
                      if(t3-1>=t4)k+=dp[t1][t2][t3-1][t4][t5];
                      if(t2-1>=t3)k+=dp[t1][t2-1][t3][t4][t5];
                      if(t1-1>=t2)k+=dp[t1-1][t2][t3][t4][t5];
                      
                    }
                  }
            }
          }
        }
        cout<<dp[l[1]][l[2]][l[3]][l[4]][l[5]]<<'\n';
      }
      return 0;
}