题意分析

题目描述了一位游客在圣安东尼奥的河边步道品尝玛格丽塔鸡尾酒的情景。游客有一笔预算金额 $D$，需要在 $V$ 家不同的商家购买玛格丽塔。每家商家的价格已知，游客可以选择的购买组合需要满足以下条件：

1. 预算限制：组合中所有商家的价格总和不超过 $D$。
2. 未使用金额限制：未使用的金额（即 $D - \text{总价格}$）必须小于任何未被选中的商家的价格。换句话说，如果剩下的钱足够购买任何一家未被选中的商家的玛格丽塔，那么这个组合是无效的。

目标是计算满足以上条件的组合数量。

解题思路

关键点分析

1. 组合选择：从 $V$ 家商家中选择若干家，每家最多选一次。
2. 总价格限制：选中的商家价格总和 $S \leq D$。
3. 剩余金额限制：$D - S < \min(\text{未选中的商家价格})$。这意味着如果剩下的钱足够购买任何一家未选中的玛格丽塔，那么这个组合无效。

解决步骤

1. 排序价格：首先将所有商家的价格按升序排序。这样我们可以方便地处理未选中的最小价格。
2. 动态规划：使用动态规划来计算在给定预算内选择某些商家的组合数。定义 $dp[i][j]$ 表示前 $i$ 个商家中选择总价格为 $j$ 的组合数。
3. 组合验证：对于每个可能的总价格 $S \leq D$，我们需要验证剩余金额 $D - S$ 是否小于所有未选中商家的最小价格。由于价格已排序，未选中的最小价格就是第一个未被选中的商家的价格。
4. 累计有效组合：遍历所有可能的总价格 $S$，对于每个 $S$，找到最小的未选中价格 $p$（即第一个未被选中的价格），并检查 $D - S < p$。如果满足，则将对应的组合数累加到结果中。

动态规划转移

• 初始化：$dp[0][0] = 1$，表示不选任何商家时总价格为 $0$ 的组合数为 $1$。
• 转移方程：对于第 $i$ 个商家（价格为 $p_i$），$dp[i][j] = dp[i-1][j] + dp[i-1][j - p_i]$（如果 $j \geq p_i$）。

验证剩余金额

• 对于每个总价格 $S$，假设我们选中了某些商家，未选中的商家中最小的价格是 $p_k$（即排序后第一个未被选中的价格）。
• 需要满足 $D - S < p_k$。为了高效计算，可以预处理排序后的价格，并对于每个 $S$，找到最小的 $p_k$ 使得 $p_k > D - S$。

算法复杂度

• 排序：$O(V \log V)$。
• 动态规划：$O(V \times D)$。
• 验证剩余金额：对于每个 $S$，可以在 $O(1)$ 或 $O(\log V)$ 时间内完成。
• 总复杂度：$O(V \log V + V \times D)$，对于 $V \leq 30$ 和 $D \leq 1000$ 是可接受的。

#include<cstdio>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
const int N=1005;
const int inf=0x3f3f3f3f;
int T,n,m,sum[N],f[N],w[N];

int main() {
    scanf("%d",&T);
    for(int t=1;t<=T;t++) {
        // 手动初始化f数组
        for(int i=0;i<N;i++) f[i] = 0;
        // 手动初始化sum数组
        for(int i=0;i<N;i++) sum[i] = 0;
        
        f[0]=1;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) scanf("%d",&w[i]);
        sort(w+1,w+n+1);
        
        if(w[1]>m) {
            printf("%d 0\n",t); 
            continue;
        }
        
        for(int i=1;i<=n;i++) sum[i]=sum[i-1]+w[i]; 
        int ans=0;
        
        for(int i=n;i>=1;i--) {
            if(m-sum[i-1]>=0) {
                int st=max(m-sum[i]+1,0); 
                for(int j=st;j<=m-sum[i-1];j++)
                    ans+=f[j];  
            }
            for(int j=m;j>=w[i];j--) 
                f[j]+=f[j-w[i]];       
        }
        printf("%d %d\n",t,ans);
    }
    return 0;
}