2020年河北省程序设计大赛 7-7 划分

#include
#define int long long
#define x first
#define y second
using namespace std;/*** 状态表示f[i]为以i结尾的数组有多少个合法数组* 分两个集合选和不选第i个数，如果不选 f[i] = max(f[i], f[i - 1])* 如果选，就从0 - i扫一遍，是否有第j个数，满足sum(i, j) 在[l, r] 之间，那么f[i] = max(f[i], f[j - 1] + 1)**/void solve()
{int n, l, r;cin >> n >> l >> r;vector<int> a(n + 1), s(n + 1), dp(n + 1);for (int i = 1; i <= n; i++) cin >> a[i];// 处理前缀和for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];for (int i = 1; i <= n; i++){// 如果选第i个数，就需要找到前面的某一个j，使得满足sum(i, j) 在[l, r] 之间for (int j = 1; j <= i; j++){if (s[i] - s[j - 1] >= l && s[i] - s[j - 1] <= r) dp[i] = max(dp[i], dp[j - 1] + 1);}// 如果不选，那么就是dp[i - 1];dp[i] = max(dp[i], dp[i - 1]);}cout << dp[n] << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);int T = 1;cin >> T;while (T--) solve();return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！