- 元素和
题目ID：7688必做题100分
最新提交：
Time Limit Exceeded
0 分
历史最高：
Time Limit Exceeded
0 分
时间限制: 1000ms
空间限制: 524288kB
题目描述
Bessie 有一个集合，集合中有一些元素，她发现某些元素可以表示成另几个元素的和，如 {1,2,3} 中就有 3=1+2，而 3=2+1被看成与 3=1+2 是相同的式子。
Bessie 想知道她的集合中有多少组这样的元素和。
输入格式
第一行为 t，表示测试数据组数。
接下来 t 行，每行表示一组测试数据。其中第一个数 m，表示集合元素的个数，接下来 m 个不同的整数 x 分别表示集合元素。
输出格式
对于每个输入数据，输出一个整数，表示其中元素和的个数。
输入输出样例
输入
3
3 1 2 3
3 1 2 5
6 1 2 3 5 4 6
输出
1
0
7
数据规模与约定1≤t≤10,1≤m≤30,1≤x≤1000
本帅哥的代码
#include <bits/stdc++.h>
using namespace std;
void solve() {
int m, x[35], f[35][1005] = {0}, ans = 0;
cin >> m;
for (int i = 1; i <= m; i++) {
cin >> x[i];
}
f[0][0] = 1;
sort(x + 1, x + m + 1);
for (int i = 1; i <= m; i++) {
for (int j = x[1]; j <= x[m]; j++) {
if (j <= x[i]) {
continue;
}
f[i][j] = f[i-1][j] + f[i-1][j-x[i]];
}
}
for (int i = 1; i <= m; i++) {
ans += f[i-1][x[i]];
}
cout << ans << endl;
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
