平台电商网站开发,宁波网站制作作,com域名的网址有哪些,广州建设行业网站传送门
题意#xff1a;给一个长度为NNN的序列aaa,从中选出kkk个#xff0c;定义一个序列的美丽度为最接近的两个数的差的绝对值#xff0c;求所有方案的美丽度之和模998244353998244353998244353。 N≤1000,ai≤100000N \leq 1000,a_i \leq100000N≤1000,ai≤100000
显…传送门
题意给一个长度为NNN的序列aaa,从中选出kkk个定义一个序列的美丽度为最接近的两个数的差的绝对值求所有方案的美丽度之和模998244353998244353998244353。
N≤1000,ai≤100000N \leq 1000,a_i \leq100000N≤1000,ai≤100000
显然先排个序枚举美丽度求方案数。
设美丽度为ddd我们希望求出选出kkk个数相邻两数的差不小于ddd
显然可以dp
dp(i,j)dp(i,j)dp(i,j)表示前iii个选jjj个且最后一个必选的方案数。
dp(i,j)∑ai−ak≥ddp(k,j−1)dp(i,j)\sum_{a_i-a_k\geq d}dp(k,j-1)dp(i,j)ai−ak≥d∑dp(k,j−1)
一个前缀和就完事了
总复杂度O(annk)O(a_nnk)O(annk)
冷静分析我们发现随着ddd的增加数会越来越小。当到达一定的程度后就是000了。
容易算出这个值是⌊an−a1k−1⌋\lfloor\frac{a_n-a_1}{k-1}\rfloor⌊k−1an−a1⌋
所以只用枚举这么多个
复杂度O(an−a1k−1nk)O(ann)O(\frac{a_n-a_1}{k-1}nk)O(a_nn)O(k−1an−a1nk)O(ann)
#include iostream
#include cstdio
#include cstring
#include cctype
#include algorithm
#define MAXN 1005
#define MAXM 100005
using namespace std;
typedef long long ll;
const int MOD998244353;
inline int add(const int x,const int y){return xyMOD? xy-MOD:xy;}
inline int dec(const int x,const int y){return xy? xMOD-y:x-y;}
int a[MAXN];
int dp[MAXN][MAXN],ans[MAXM];
int main()
{int n,k;scanf(%d%d,n,k);for (int i1;in;i) scanf(%d,a[i]);sort(a1,an1);int mx(a[n]-a[1])/(k-1);for (int d1;dmx;d){for (int i1;ik;i)for (int j1;jn;j)dp[i][j]0;for (int i1;in;i) dp[1][i]1;for (int i2;ik;i){int pos0,sum0;for (int j1;jn;j){while (posna[j]-a[pos1]d)sumadd(sum,dp[i-1][pos]); dp[i][j]sum; } }for (int i1;in;i) ans[d]add(ans[d],dp[k][i]);}int res0;for (int i1;imx;i) resadd(res,ans[i]);printf(%d\n,res);return 0;
}这题交了四发是个憨憨。
