打工

DP

---

题面

有$n$个人,可以分任意数量(不超过$n$)的组，相同组的人用相同数字来表示。如果有多种表示,我们认为字典序最小的表示才是有效的。
询问某一表示是所有分组方式中的第几小。

• $30pts\ n\leq14$
• $50pts\ ask\{1,2,3...n\}$
• $100pts\ n\leq10000$

解析

特别提醒：请将“表示”看作名词
看着这道题就想起了分组一题，两题分组的方式完全一样。

$30pts$算法

每加入一个数，只有两种方案：新建组$or$加入已有组
以此$DFS$暴力枚举每一种方案，看该方案是第几个。

$50pts$算法

这相当于问$n$个人有多少种分组方式有木有。。。
预处理$n$个人分为$m$组（或者说这$n$个人 所属组的编号 的最大值）的方案数$dp[n][m]$。
方程为

$$dp[i][j]=dp[i-1][j-1]+dp[i-1][j]*j$$
则 $$ans=\sum_{i=1}^{n}dp[n][i]$$

$100pts$算法

我考场上一开始想到的是$50pts$算法。
但这种算法不好回答这个表示是第几个。
试着比较两个表示$1\ 1\ 1\ 1\ $和$1\ 2\ 3\ 4\ $，我们一般是怎样计算两者间差多少个表示来着？
就是不断往最后一位$+1$，如果超过表示中的最大值，就向前“进位”。
由此，我们可以看出，当一位增加时，后面（整个数）经历了多少种表达方式，而这本质是后面的数有多少种分组方式。
如从$1\ 2\ 2\ 4\ $到$1\ 2\ 3\ 4\ $，经历$5$种。
我们求的也就是询问的表示经历了多少种。

于是我们就应该预处理这玩意儿。
$DP$状态不变，但应从后往前枚举。
边界$dp[n][i]=i+1$
方程$dp[i][j]=dp[i+1][j+1]+dp[i+1][j]*j$
然后就像$j$进制数转十进制一般（都是数位上的数乘权值的和），从前往后，统计

$$\sum_{i=2}^{n-1}(a[i]-1)*f[i+1][max\{a[1],a[2]...,a[i-1]\}]+a[n]$$
就是询问表示经历的方案数。

这个$DP$状态就是用来与前面对接的，反映前面的状态，却存着后面的结果，所以有这个$max$。
不计$a[i]$是因为$a[i]$贡献反映在系数里。
当然可以滚掉一维。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=1e4+100,mod=1e6+7;
int n,a[N],tong[N],tot,sum,ysn=1,dp[N][N],ans;
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void ok(re int &x){while(x>=mod) x-=mod;}
int main()
{
  n=gi();
  fp(i,1,n) a[i]=gi();
  fp(i,1,n-1) dp[n][i]=i+1;
  fq(i,n-1,1)
    fq(j,i,1)
    dp[i][j]=dp[i+1][j+1]+1ll*dp[i+1][j]*j%mod,ok(dp[i][j]);
  fp(i,2,n-1)
    {
      ans=ans+1ll*dp[i+1][ysn]*(a[i]-1)%mod,ok(ans);
      if(a[i]>ysn) ysn++;
    }
  ans=ans+a[n];ok(ans);
  printf("%d\n",ans);
  fclose(stdin);
  fclose(stdout);
  return 0;
}