P7519 滚榜（状压 dp + 贪心）

Description

State

Input

Output

Solution

Code

Description

Alice 围观了一场 ICPC 竞赛的滚榜环节。本次竞赛共有 $n$ 支队伍参赛，队伍从 $1～n$ 编号，$i$ 号队伍在封榜前通过的题数为 $a_i$。排行榜上队伍按照过题数从大到小进行排名，若两支队伍过题数相同，则编号小的队伍排名靠前。

滚榜时主办方以 $b_i$ 不降的顺序依次公布了每支队伍在封榜后的过题数 $b_i$（最终该队伍总过题数为 $a_i+b_i$），并且每公布一支队伍的结果，排行榜上就会实时更新排名。Alice 并不记得队伍被公布的顺序，也不记得最终排行榜上的排名情况，只记得每次公布后，本次被公布结果的队伍都成为了新排行榜上的第一名，以及所有队伍在封榜后一共通过了 $m$ 道题（即 ${\sum }_{i=1}^n{b}_i=m$）。

现在 Alice 想请你帮她算算，最终排行榜上队伍的排名情况可能有多少种。

State

\(1<=n<=13\)

\(1<=m<=500\)

\(0<=a_i<=10^4\)

Input

3 6
1 2 1

Output

5

Solution

由于最后只与排名有关，贪心考虑，每个队伍冲到榜首只花费最少的过题数，如果还有剩余，全放在最后一个人身上

这样 \(dp[s][i][k]\) ： 表示状态 \(s\) 上为 \(1\) 的已经滚榜完毕，且 \(i\) 为当前榜首，总花费为 \(k\) 的种类数

\(dp\) 转移方程为 \(dp[s][i][k]=\sum dp[s\ xor \ (1 << i)][j][cost(i,j)]\)

最后答案为 \(\sum{dp[1..1][1-n][0-m]}\)

Code

const int M = 500 + 5;
const int S = (1 << 13) + 5;
const int N = 15 + 5;

    int n, m, k, _;
    int a[N];
    ll dp[S][N][M];

signed main()
{
    // IOS;
    while(~ sdd(n, m)){
        int maxx = -1;
        rep(i, 1, n){
            sd(a[i]);
            if(a[i] > a[maxx]){
                maxx = i;
            }
        }
        for(int i = 1; i <= n; i ++){
            int need = a[maxx] - a[i];
            if(maxx < i) need ++;
            if(need * n <= m){
                dp[1 << i - 1][i][need * n] = 1;
            }
        }
        int all = 1 << n;
        for(int s = 1; s < all; s ++){
            int popcount = __builtin_popcount(s);
            if(popcount == 1) continue;
            for(int i = 1; i <= n; i ++){
                if((s & (1 << i - 1)) == 0) continue;
                for(int j = 1; j <= n; j ++){
                    int now = s ^ (1 << i - 1);
                    if(i != j && (now & (1 << j - 1)) == (1 << j - 1)){
                        int need = a[j] - a[i];
                        if(i > j) need ++;
                        need = max(need * (n - popcount + 1), 0);
                        for(int k = need; k <= m; k ++){
                            dp[s][i][k] += dp[now][j][k - need];
                        }
                    }
                }
            }
        }
        ll ans = 0;
        for(int i = 1; i <= n; i ++){
            for(int k = 0; k <= m; k ++){
                ans += dp[all - 1][i][k];
                // dbg(dp[all - 1][i][k]);
            }
        }
        pll(ans);
    }
    return 0;
}