A17433. 多边形（polygon）
填空题
困难
知识点
题目描述
多边形（polygon）
题目描述
小 R 喜欢玩小木棍。小 R 有 n 根小木棍，第 i（1≤i≤n）根小木棍的长度为 ai。
小 X 希望小 R 从这 n 根小木棍中选出若干根小木棍，将它们按任意顺序首尾相连拼成一个多边形。小 R 并不知道小木棍能拼成多边形的条件，于是小 X 直接将条件告诉了他：对于长度分别为 l1,l2,…,lm 的 m 根小木棍，这 m 根小木棍能拼成一个多边形当且仅当 m≥3 且所有小木棍的长度之和大于所有小木棍的长度最大值的两倍，即
由于小 R 知道了小木棍能拼成多边形的条件，小 X 提出了一个更难的问题：有多少种选择小木棍的方案，使得选出的小木棍能够拼成一个多边形？你需要帮助小 R 求出选出的小木棍能够拼成一个多边形的方案数。两种方案不同当且仅当选择的小木棍的下标集合不同，即存在 1≤i≤n，使得其中一种方案选择了第 i 根小木棍，但另一种方案未选择。由于答案可能较大，你只需要求出答案对 998,244,353 取模后的结果。
输入格式
从文件 polygon.in 中读入数据。
输入的第一行包含一个正整数 n，表示小 R 的小木棍的数量。
输入的第二行包含 n 个正整数 a1,a2,…,an，表示小 R 的小木棍的长度。
输出格式
输出到文件 polygon.out 中。
输出一行一个非负整数，表示小 R 选出的小木棍能够拼成一个多边形的方案数对 998,244,353 取模后的结果。
样例 1 输入
5
1 2 3 4 5样例 1 输出
9样例 1 解释
共有以下 9 种选择小木棍的方案，使得选出的小木棍能够拼成一个多边形：
- 选择第 2,3,4 根小木棍，长度之和为 2+3+4=9，长度最大值为 4；
- 选择第 2,4,5 根小木棍，长度之和为 2+4+5=11，长度最大值为 5；
- 选择第 3,4,5 根小木棍，长度之和为 3+4+5=12，长度最大值为 5；
- 选择第 1,2,3,4 根小木棍，长度之和为 1+2+3+4=10，长度最大值为 4；
- 选择第 1,2,3,5 根小木棍，长度之和为 1+2+3+5=11，长度最大值为 5；
- 1,2,4,5 根小木棍，长度之和为 1+2+4+5=12，长度最大值为 5；
- 选择第 1,3,4,5 根小木棍，长度之和为 1+3+4+5=13，长度最大值为 5；
- 选择第 2,3,4,5 根小木棍，长度之和为 2+3+4+5=14，长度最大值为 5；
- 选择第 1,2,3,4,5 根小木棍，长度之和为 1+2+3+4+5=15，长度最大值为 5。
样例 2 输入
5
2 2 3 8 10样例 2 输出
6共有以下 6 种选择小木棍的方案，使得选出的小木棍能够拼成一个多边形：
- 选择第 1,2,3 根小木棍，长度之和为 2+2+3=7，长度最大值为 3；
- 选择第 3,4,5 根小木棍，长度之和为 3+8+10=21，长度最大值为 10；
- 选择第 1,2,4,5 根小木棍，长度之和为 2+2+8+10=22，长度最大值为 10；
- 选择第 1,3,4,5 根小木棍，长度之和为 2+3+8+10=23，长度最大值为 10；
- 选择第 2,3,4,5 根小木棍，长度之和为 2+3+8+10=23，长度最大值为 10；
- 选择第 1,2,3,4,5 根小木棍，长度之和为 2+2+3+8+10=25，长度最大值为 10。
参考答案
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int MAXN = 5005;
int a[MAXN];
int cnt[MAXN][MAXN];
int dp[MAXN];
int n;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + 1 + n);
cnt[1][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= 5001; j++) {
cnt[i+1][j] = (cnt[i+1][j] + cnt[i][j]) % mod;
cnt[i+1][min(j+a[i],5001)] = (cnt[i+1][min(j+a[i],5001)] + cnt[i][j]) % mod;
}
}
//求dp
for (int i = 1; i <= n; i++) {
dp[i] = dp[i-1];
for (int j = a[i]+1; j <= 5001; j++) dp[i] = (dp[i] + cnt[i][j]) % mod;
}
cout << dp[n];
return 0;
}
上一题
下一题