题目链接
题目大意
一共有n个石子 每个石子i 有重量ai 你需要将这些石子分成两份 其中一份是你的 需要满足 你的这一份重量大于等于剩下那一份 而且你的这一份石子去掉任意一个石子后会小于等于剩下那一份
题目思路
注意 你的这一份石子去掉任意一个石子后会小于等于剩下那一份 等价于去掉你的这一份石子中最小的石子后 会小于等于剩下那一份
那我们就从这个最小的石子入手 对于所有的石子重量先进行排序
从1-n开始逐个确定当前位为已选石子中最小的那个石子
那么 假设i后面要选择的给自己的石子量为x 给剩下选择的石子量为y
sum存石子重量的前缀和
则对于每一个 i 有
x + a[i] >= y + sum[i-1] (你的这一份重量大于等于剩下那一份 )
x + a[i] -a[i] <= y +sum[i-1] （而且你的这一份石子去掉任意一个石子后会小于等于剩下那一份）
化简后：
(sum[n]-2*a[i]) / 2 <= x <= (sum[n]-a[i]) / 2
下一步只需要知道 对于每一个i里后面的石子和可能的x值 情况数是多少 加起来即为答案
然后就是个简单的背包转移
设一个二维数组dp [ i ][ j ] 表示从位置 i 到 n 石子和为 j 的方案数
这里用滚动数组也可以 但是没必要
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int maxn=3e2+10;
const int maxm=150000+10;
int dp[maxn][maxm];
ll t,n,sum;
ll a[maxn];
void init()
{sum=0;memset(dp,0,sizeof(dp));
}
int main()
{cin>>t;while(t--){cin>>n;init();for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1);for(int i=1;i<=n;i++)sum+=a[i]; dp[n+1][0]=1;for(int i=n;i>=1;i--){for(int j=0;j<=150000;j++){dp[i][j]=dp[i+1][j];if(j-a[i]>=0){dp[i][j]=(dp[i][j]+dp[i+1][j-a[i]])%mod;}}}ll ans=0; for(int i=1;i<=n;i++){for(ll j=(sum+1)/2-a[i];j*2<=sum-a[i];j++){if(j<0)continue;ans=(ans+dp[i+1][j])%mod;}}cout<<ans%mod<<endl;}return 0;
}