傳送門

題意：給一個長度為$N$的序列$a$,從中選出$k$個，定義一個序列的美麗度為最接近的兩個數的差的絕對值，求所有方案的美麗度之和模$998244353$。

$N\le 1000,a_i\le 100000$

顯然先排個序，枚舉美麗度求方案數。

設美麗度為$d$，我們希望求出選出$k$個數，相鄰兩數的差不小于$d$

顯然可以dp

$dp(i,j)$表示前$i$個選$j$個且最后一個必選的方案數。

$$dp(i,j)=\sum _{a_i?a_k\ge d}dp(k,j?1)$$

一個前綴和就完事了

總復雜度$O(a_{n}nk)$

冷靜分析，我們發現隨著$d$的增加，數會越來越小。當到達一定的程度后就是$0$了。

容易算出這個值是$?\frac{a_n?a_1}{k?1}?$

所以只用枚舉這么多個

復雜度$O(\frac{a_n?a_1}{k?1}nk)=O(a_{n}n)$

#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 MOD=998244353; inline int add(const int& x,const int& y){return x+y>=MOD? x+y-MOD:x+y;} inline int dec(const int& x,const int& y){return x<y? x+MOD-y:x-y;} int a[MAXN]; int dp[MAXN][MAXN],ans[MAXM]; int main() {int n,k;scanf("%d%d",&n,&k);for (int i=1;i<=n;i++) scanf("%d",&a[i]);sort(a+1,a+n+1);int mx=(a[n]-a[1])/(k-1);for (int d=1;d<=mx;d++){for (int i=1;i<=k;i++)for (int j=1;j<=n;j++)dp[i][j]=0;for (int i=1;i<=n;i++) dp[1][i]=1;for (int i=2;i<=k;i++){int pos=0,sum=0;for (int j=1;j<=n;j++){while (pos<n&&a[j]-a[pos+1]>=d)sum=add(sum,dp[i-1][++pos]); dp[i][j]=sum; } }for (int i=1;i<=n;i++) ans[d]=add(ans[d],dp[k][i]);}int res=0;for (int i=1;i<=mx;i++) res=add(res,ans[i]);printf("%d\n",res);return 0; }

這題交了四發，是個憨憨。

總結

以上是生活随笔為你收集整理的【CF1189F】Array Beauty【dp】【复杂度玄学优化】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。