题解：数列划分

【题目描述】

给出 \(n\) 项的数列，要求将数列划分成若干段，且每一段之和都不超过 \(s\)。 求一共有多少种满足要求的划分方法。

方法数很大，只要求输出除以 \(10^9\) 的余数。

【输入】

第 \(1\) 行，两个正整数 \(n,s\)

第 \(2\) 行，\(n\) 个正整数 \(a_1,a_2,⋯ ,a_n\)

【输出】

一个整数，划分方法数除以 \(10^9\) 的余数。

【输入样例】

5 3
1 2 1 1 1

【输出样例】

10

【代码详解】

#include<iostream>
#include<algorithm>
using namespace std;const int MOD = 1e9;  // 模数
int n, s, a[1005], sa[1005], dp[1005];  // n: 数字个数，s: 最大和限制，a: 原数组，sa: 前缀和数组，dp: 动态规划数组int main()
{cin >> n >> s;  // 读入n和sfor (int i = 1; i <= n; i++){cin >> a[i];  // 读入第i个数字sa[i] = sa[i - 1] + a[i];  // 计算前缀和}dp[0] = 1;  // 空子数组有1种划分方式for (int i = 1; i <= n; i++)  // 遍历每个位置{for (int j = i; j >= 1; j--)  // 向前遍历可能的划分点{// 检查从j到i的子数组和是否不超过sif (sa[i] - sa[j - 1] <= s){// 如果满足条件，将dp[j-1]的方案数加到dp[i]上dp[i] = (dp[i] + dp[j - 1]) % MOD;}}}cout << dp[n];  // 输出前n个元素的划分方案总数return 0;
}

【运行结果】

5 3
1 2 1 1 1
10