博客食用更佳~
https://www.cnblogs.com/czyty114/p/14766344.html

$\;$
题意： https://www.luogu.com.cn/problem/P7519

Solution

暴力

$\;$
暴力枚举每种排列，显然排名是按照$b_i$不降的顺序也单调升高
所以只需让当前队伍排第一的前提下让$b_i$的尽可能的小即可。
如果发现$\sum b_i <=m$，一定是存在一种方案的（让最后一个队伍过题数更多就行了）
$\;$

状压dp

$\;$
考虑设计状态。
首先目前已选队伍的集合S一定得有，然后是目前总过题数$k$
显然，你还关心上个队伍的编号和$b_j$
因为按照暴力的贪心思路，我们要让当前的$b_i$尽可能的小。假设上个队伍为$j$
即：$a_i+b_i\geq a_j+b_j,\;b_i\geq a_j+b_j-a_i$
但这样的时间复杂度是
$O(2^n \times n^2 \times m^2)$的
考虑简化状态。
再次考虑$b_i$的不降性，得到：$b_i=max(b_j, b_j+a_j-a_i)$，即：$b_i=b_j+max(0,a_j-a_i)$
最终我们一定选了$n$支队伍，那么$\sum b_i$一定是
$\sum max(0,a_j - a_i) \times (n- p_i +1)$
$p_i$代表$i$队伍是第几个选的。
换句话来说，第$i$支队伍对答案的贡献可以简化为$max(0,a_j -a_i)\times (n-p_i+1)$
所以我们没有必要知道$b_i$具体的值是多少，而是只需要知道他对最终答案的贡献是多少就可以了。
这实质是一个提前算贡献的思想（不关心过程，只关心它对最终结果造成的影响）
所以就可以把上个队伍$b_j$给删去。
而现在的$k$就不是目前选题总个数了（而是最终对答案影响的贡献）
最终复杂度：$O(2^n \times n^2 \times m)$

Code

#include <bits/stdc++.h>

const int N = 13, M = 505;

#define ll long long
int n, m, a[N];

ll f[1 << N][N + 1][M];
int main() {
    scanf("%d%d", &n, &m);
    int t = n;
    for (int i = 0; i < n; i ++) {
        scanf("%d", &a[i]);
        if (a[i] > a[t]) t = i;
    }
    for (int i = 0; i < n; i ++) {
        int add = n * (a[t] - a[i] + (i > t));
        if (add <= m) f[1 << i][i][add] = 1;
    }
    for (int i = 1; i < (1 << n); i ++) {
        int cnt = 0;
        for (int j = 0; j < n; j ++) if (i >> j & 1) cnt ++;
        for (int j = 0; j < n; j ++) if (i >> j & 1)
            for (int k = 0; k <= m; k ++) 
                for (int l = 0; l < n; l ++) if ((i | (1 << l)) != i) {
                    int add = (n - cnt) * std::max(0, a[j] - a[l] + (l > j));
                    if (k + add <= m) f[i | (1 << l)][l][k + add] += f[i][j][k];
                }
    }   
    ll ans = 0;
    for (int i = 0; i < n; i ++) 
        for (int j = 0; j <= m; j ++)
        ans += f[(1 << n) - 1][i][j];
    printf("%lld", ans);
    return 0;           
}