专栏文章

polygon 题解

aa_foolish_OIer
P14360题解参与者 19已保存评论 20

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
20 条
当前快照
1 份
快照标识符
@minfszs6
此快照首次捕获于
2025/12/02 01:42
3 个月前
此快照最后确认于
2025/12/02 01:42
3 个月前
查看原文
有史以来最简单的 T4。
直接 dfs 可以拿下 4040。
考虑将 max⁡\max 拆掉，可以先对 aa 进行排序，那么前 ii 项的最大值为 aia_i，对于 ∑\sum，可以使用背包求解。
至于边数 ≥3\ge 3 这个限制，再加一维度表示选了 kk 个木棍即可，kk 只需要枚举到 33，所以记 fi,j,kf_{i,j,k} 表示前 ii 项和为 jj 选了 kk 根木棍即可。
直接这么做是 O(n2V)O(n^2V) 的，考虑优化。
注意到 22 倍的 max⁡\max 是不会超过 10410^4，所以对于 ∑\sum 那一维，只需要枚举到 10410^4，时间复杂度 O(nV)O(nV)，大约带 88 倍常数。
CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'

const int N = 5e3 + 10;
const int M = 1e4 + 10;
const int mod = 998244353; 

int n,v;
int a[N];
int dp[2][M][5];
 
void add (int &x,int y){
	x += y;
	if (x >= mod) x -= mod;
}
void solve(){
	cin >> n; v = 0;
	for (int i = 1 ; i <= n ; i++) cin >> a[i],v = max(v,a[i]);
	sort(a + 1,a + n + 1);
	v = v * 2 + 1;
	dp[0][0][0] = 1;
	int cur = 0,ans = 0;
	for (int i = 0 ; i < n ; i++){
		int nxt = (cur ^ 1);
		for (int j = 0 ; j <= v ; j++){
			for (int k = 0 ; k <= 3 ; k++){
				if (!dp[cur][j][k]) continue;
				int jj = min(v,j + a[i + 1]),kk = min(k + 1,3ll);
				add(dp[nxt][jj][kk],dp[cur][j][k]);
				if (jj > 2 * a[i + 1] && kk == 3) add(ans,dp[cur][j][k]);
				add(dp[nxt][j][k],dp[cur][j][k]);
				dp[cur][j][k] = 0;
			} 
		}
		cur ^= 1; 
	}
	cout << ans << endl;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int T = 1; //cin >> T;
	while (T--) solve();
	return 0; 
}

评论

共 20 条评论，欢迎与作者交流。

正在加载评论...