POJ P2279 Mr. Young's Picture Permutations 题解

每日一题 day14 打卡

Analysis

五维dp
f[a1,a2,a3,a4,a5]表示各排从左端起分别占了a1,a2,a3,a4,a5个人时合影方案数量
然后我们枚举a1,a2,a3,a4,a5从0开始到N1,N2……N5
若a1 < N1
若a2 < N2&a1 > a2
若a3 < N3&a2 > a3
……(以此类推)

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define int long long 
 6 #define maxn 30+10
 7 #define maxk 5+10
 8 using namespace std;
 9 inline int read() 
10 {
11     int x=0;
12     bool f=1;
13     char c=getchar();
14     for(; !isdigit(c); c=getchar()) if(c=='-') f=0;
15     for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+c-'0';
16     if(f) return x;
17     return 0-x;
18 }
19 inline void write(int x)
20 {
21     if(x<0){putchar('-');x=-x;}
22     if(x>9)write(x/10);
23     putchar(x%10+'0');
24 }
25 int k;
26 int a[maxk],s[maxk];
27 int dp[maxn][maxn][maxn][maxn][maxn];
28 signed main()
29 {
30     while(1)
31     {
32         memset(dp,0,sizeof(dp));
33         memset(a,0,sizeof(a));
34         k=read();
35         if(k==0) return 0;
36         for(int i=1;i<=k;i++) a[i]=read();
37         dp[0][0][0][0][0]=1;
38         for(s[1]=0;s[1]<=a[1];s[1]++)
39             for(s[2]=0;s[2]<=a[2];s[2]++)
40                 for(s[3]=0;s[3]<=a[3];s[3]++)
41                     for(s[4]=0;s[4]<=a[4];s[4]++)
42                         for(s[5]=0;s[5]<=a[5];s[5]++)
43                             for(int i=1;i<=k;i++)
44                             {
45                                 if(s[i]<a[i]&&(i==1||s[i-1]>s[i]))
46                                 {
47                                     int x1=s[1],x2=s[2],x3=s[3],x4=s[4],x5=s[5];
48                                     s[i]++;
49                                     dp[s[1]][s[2]][s[3]][s[4]][s[5]]+=dp[x1][x2][x3][x4][x5];
50                                     s[i]--;
51                                 }
52                             }
53         write(dp[a[1]][a[2]][a[3]][a[4]][a[5]]);
54         printf("
");
55     }
56     return 0;
57 }

请各位大佬斧正~~（反正我不认识斧正是什么意思）~~