1 条题解
-
0
C++ :
#include<bits/stdc++.h> using namespace std; #define LL long long const LL N=51,M=2501; LL n,k,a[N],f[N][M][N]; int main(){ scanf("%lld%lld",&n,&k); for(LL i=1;i<=n;i++) scanf("%lld",&a[i]); for(LL i=0;i<N;i++) f[i][0][0]=1; for(LL i=1;i<=n;i++){ for(LL j=0;j<M;j++){ for(LL k=0;k<=i;k++){ f[i][j][k]=f[i-1][j][k]; if(j>=a[i]&&k>=1) f[i][j][k]+=f[i-1][j-a[i]][k-1]; } } } LL ans=0; for(LL i=1;i<=n;i++){ for(LL j=0;j<i;j++){ LL sum=(j+1)*k-a[i]; if(sum>=0) ans+=f[i-1][sum][j]; } } printf("%lld\n",ans); }
Python :
# coding=utf-8 N, A = map(int, input().split()) Xs = list(map(int, input().split())) Ys = [X-A for X in Xs] sumPos = sumNeg = 0 for Y in Ys: if Y >= 0: sumPos += Y else: sumNeg += Y #print('# sumPos:', sumPos, '/ sumNeg:', sumNeg) LLL = sumPos - sumNeg + 1 dp = [0] * (LLL+1) dp[0] = 1 for Y in Ys: dp2 = dp[:] for s in range(sumNeg, sumPos+1): dpNow = dp[s] if dpNow == 0: continue s2 = s+Y dp2[s2] += dpNow dp = dp2 # print('# Y:', Y, '/ dp:', dp) ans = dp[0] - 1 print(ans)
信息
- ID
- 20988
- 时间
- 2000ms
- 内存
- 128MiB
- 难度
- 8
- 标签
- (无)
- 递交数
- 95
- 已通过
- 15
- 上传者