题目描述
难度分:$2237$
输入$n(3 \leq n \leq 300)$和长为$n$的数组$a(1 \leq a_i \leq 300)$。
把每个$a_i$都涂成红/绿/蓝三种颜色中的一种。(相当于把$a$分成$3$个子序列)
记红色元素和为R
,绿色元素和为G
,蓝色元素和为B
。
问:有多少种涂色方案,使得R
,G
,B
组成了一个非退化三角形的三条边。模$998244353$。
注:非退化三角形即面积为正的三角形,或者说三顶点不共线的三角形。
输入样例$1$
4
1
1
1
2
输出样例$1$
18
输入样例$2$
6
1
3
2
3
5
2
输出样例$2$
150
输入样例$3$
20
3
1
4
1
5
9
2
6
5
3
5
8
9
7
9
3
2
3
8
4
输出样例$3$
563038556
算法
01
背包
这个题如果正着来做的话状态数量是很庞大的,因此正难则反,求不能构成三角形的方案数会简单一些(因为不能构成三角形的限制较少,不用存储那么多状态)。令$s=\Sigma_{i=1}^{n}a_i$,如果其中有一种颜色的元素累加和不小于$[\frac{s}{2}]$($[.]$表示对$.$向下取整),那肯定就构不成三角形了。
状态定义
此时问题转化成了从$n$个元素中选择若干个,使得元素和大于等于$[\frac{s}{2}]$的方案数。定义$f[i][j]$为从前$i$个元素中选择若干个,使得元素和大于等于$j$的方案数。
状态转移
每个元素$a_i$可以选择是否染成参考颜色(红绿蓝都有可能),此时有状态转移方程
$f[i][j]=f[i-1][j] \times 2 + f[i-1][j-a_i]$
因为$a_i$不涂成参考颜色时,它可以涂成另外两种颜色,所以不选的时候状态要乘以$2$。而单独考虑某种颜色的累加和要大于$j$时,有三种颜色可供选择,所以$f[0][j]=3$。
这里需要注意一点,当$s$为偶数时,如果考虑选择若干个数染成红色,使得这些数的总和不小于$\frac{s}{2}$,会存在R
$=$G
的情况,再考虑选择若干个数染成绿色时,又统计了一遍这种情况,最终计算对立事件时会多减一次,要加回来。
因此还需要定义一个状态$g[i][j]$,表示从前$i$个元素中选数,累加和恰好为$j$的方案数,状态转移就是01
背包的状态转移。当$s$是奇数时,答案是$3^n-f[n][[\frac{s+1}{2}]]$;$s$是偶数时,答案是$3^n-f[n][[\frac{s+1}{2}]]+g[n][[\frac{s}{2}]]$。
复杂度分析
时间复杂度
体积的规模是$O(n^2)$,因此本题的背包DP
时间复杂度是$O(n^3)$。
空间复杂度
空间的消耗就是两个DP
数组,由于对第一维$i \in [1,n]$进行了优化,因此额外空间复杂度为$O(n^2)$。
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 90001, MOD = 998244353;
int n, a;
int f[N], g[N];
int main() {
scanf("%d", &n);
int s = 0;
f[0] = 3;
g[0] = 3;
int pow3 = 1;
for(int i = 1; i <= n; i++) {
scanf("%d", &a);
s += a;
for(int j = s; j >= 0; j--) {
f[j] = (f[j]*2%MOD + f[max(j - a, 0)]) % MOD;
if(j >= a) {
g[j] = (g[j] + g[j - a]) % MOD;
}
}
pow3 = (long long)pow3*3%MOD;
}
int dup = s % 2 == 0? g[s/2]: 0;
int res = (pow3 - (f[(s + 1)/2] - dup + MOD)%MOD + MOD)%MOD;
printf("%d\n", res);
return 0;
}