题目：https://nanti.jisuanke.com/t/41420
题意：给你一个集合，然后让你拆成两个集合 x,y 求满足 x>y && x-(x集合中最小值) <=y 的方案数
思路：首先我们先拆分问题，我们能不能求出集合不同值的方案数，这个很简单，我们dp[i]，i代表当前重量的方案数，然后我们很容易就能得知枚举重量 推导式就是 dp[i]=dp[i]+dp[i-a[i]],现在我们如何求出方案数我们已经知道了，我们怎么得到满足题目给的条件的方案数呢，我们知道总共集合和是多少，我们又知道当前重量是多少 ,我们只要知道当前集合的最小值x是多少， i>sum-i && （i-x）<= sum-i, 现在问题就在我们如何确定最小值，其实很简单，我们只要把物品从大到小排序，我们就能确定当前放的物品一定是当前最小，然后判断即可
#include<bits/stdc++.h> #define maxn 305 #define mod 1000000007 using namespace std; typedef long long ll; int t,n; int a[maxn]; int sum,num; int vis[maxn]; int dp[150005]; void init(){ scanf("%d",&n); memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); num+=a[i]; } } int pan(int j,int x){ if(j>=num-j&&j-x<=num-j) return 1; return 0; } int cmp(int x,int y){ return x>y; } int main(){ scanf("%d",&t); while(t--){ sum=0;num=0; init(); sort(a+1,a+n+1,cmp); dp[0]=1; for(int i=1;i<=n;i++){ for(int j=num;j>=a[i];j--){ dp[j]=(dp[j]+dp[j-a[i]])%mod; if(pan(j,a[i])){ sum=(sum+dp[j-a[i]])%mod; } } } printf("%d ",(sum+mod)%mod); } }