permu(变态考试题)

题目描述

给定一个严格递增的序列T，求有多少个T的排列S满足：∑min(T[i],S[i])=k

输入输出格式

输入格式：

第一行两个数n，k

第二行n个数，表示T

输出格式：

一个正整数表示答案，答案对10^9+9取模

输入输出样例

输入样例#1：

5 10

1 2 3 4 5

输出样例#1：

说明

30%的数据n<=10

100%的数据输入中所有数字为不超过50的正整数,k<=2500

题解：动态规划

正常的思路会想到状态压缩或暴力搜索，可以利用那个min变成普通的动归

f[i][j][k]表示前i位，还有j个数未匹配，和为k的方案数

情况1：与自己匹配，f[i+1][j][k+t[i+1]]+=f[i][j][k]

情况2：与后面的数匹配，因为严格递增，所以f[i+1][j+1][k+2*t[i+1]]+=f[i][j][k]

情况3：与前面的数匹配，再用前面的数匹配自己，f[i+1][j-1][k]+=f[i][j][k]*j*j

解释：把当前数往前匹配有j种方案，把前面的数往当前匹配有j种，根据乘法原理可知

情况4：与前面的数匹配，自己不匹配，f[i+1][j][k+t[i+1]]+=f[i][j][k]*j

解释：与前面的数匹配有j种，为什么不算后面的数，假设所有l>i且匹配了i

因为对于l，3，4情况已经算了i，所以f[l][j][k]包含了l匹配i的方案，无需重复计算

为方便定义，规定只考虑往前的匹配种数

本蒟蒻考试时完全不会，不像yzh大佬

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 long long f[][][];

 int Mod=;

 int n,k,t[];

 int main()

 {int i,j,l;

     cin>>n>>k;

     for (i=;i<=n;i++)

     {

         scanf("%d",&t[i]);

     }

     f[][][]=;

      for (i=;i<n;i++)

      {

          for (j=;j<=i;j++)

          {

              for (l=;l<=k;l++)

               if (f[i][j][l])

               {

                   f[i+][j][l+t[i+]]=(f[i+][j][l+t[i+]]+f[i][j][l])%Mod;

                   f[i+][j+][l+*t[i+]]=(f[i+][j+][l+*t[i+]]+f[i][j][l])%Mod;

                   if (j) f[i+][j-][l]=(f[i+][j-][l]+f[i][j][l]*j*j)%Mod;

                   f[i+][j][l+t[i+]]=(f[i+][j][l+t[i+]]+f[i][j][l]*j*)%Mod;

              }

         }

      }

      cout<<f[n][][k];

 }

巴特西

permu(变态考试题)

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章