題目大意：
給定一個\(n\)個數(shù)的序列\(a\)，給定一個\(x\)，其中\(a\)數(shù)組可以進(jìn)行順序的調(diào)換，每一個\(a_i\)都能使$x=x \mod a_i \(, 求最后經(jīng)過一系列計算后的\)y\(，滿足\)abs(x-y)$盡可能小，并求出方案數(shù)

QwQ 哇，一看到這個題。說實(shí)話，沒什么好的思路。

也就發(fā)現(xiàn)了幾個性質(zhì)：

1.最后的\(y\)一定小于最小的\(a_i\)

2.如果存在一個\(a_i<a_j\)，且\(i<j\) 那么\(a_j\)就沒有任何作用了，對答案沒有任何一點(diǎn)影響

那我們不妨將整個數(shù)組從大到小排序

先考慮第一問:
我們定義\(f[i][j]\)表示，考慮到第\(i\)個數(shù)，當(dāng)前的值為\(j\)是否可行，首先我們令\(f[0][x]=1\)，然后對于當(dāng)前的\(i\)，我們可以選擇用它 ，也可以選擇不用（換句話說，就是放一個比它更小的在前面，就可以實(shí)現(xiàn)不使用它了）但是后者需要滿足\(i\ !=n\) 然后分別對應(yīng)轉(zhuǎn)移即可

這里有部分分的代碼！

#include<iostream> #include<cstdio> #include<algorithm> #include<cmath>using namespace std;const int maxn = 1010; const int maxx = 5010;int f[maxn][maxx]; int a[maxn]; int n,x;inline int read() {int x=0,f=1;char ch=getchar();while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f; }bool cmp(int a,int b) {return a>b; }int main() {n=read(),x=read();for (int i=1;i<=n;i++) a[i]=read();sort(a+1,a+1+n,cmp);f[0][x]=1;for (int i=1;i<=n;i++){for (int j=0;j<=x;j++) f[i][j%a[i]]=max(f[i][j%a[i]],f[i-1][j]);if (i!=n) for (int j=0;j<=x;j++) f[i][j]=max(f[i][j],f[i-1][j]);}for (int i=x;i>=0;i--) if (f[n][i]) {cout<<i<<endl<<0<<endl;return 0;}return 0; }

那么加上第二問呢，該怎么解決呢。

看了一些排列組合的題解，不過并不知道怎么做呀。倒是有一種更好理解的方法QwQ

我們令\(g[i][j]\)表示處理第\(i\)個數(shù)，當(dāng)前值是\(j\)的方案數(shù)

如果我們使用這個點(diǎn)\(g[i][j \mod a_i ]+=g[i-1][j]\)（說明他待在當(dāng)前的位置，且后面比他小的位置，都在他后面

如果不用\(g[i][j]=g[i-1][j]*(n-i)\) （表示他可以和他之后的任意一個比他小的數(shù)換位置，都不會使用這個點(diǎn)）（或者理解為他有\(n-i\)個空隙可以插進(jìn)去

直接上代碼

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath>using namespace std;inline int read() {int x=0,f=1;char ch=getchar();while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f; }const int maxn = 1010; const long long mod = 998244353;int f[maxn][5010]; long long g[maxn][5010]; int n,x; int a[maxn];bool cmp (int a,int b) {return a>b; }int main() {scanf("%d%d",&n,&x);for (int i=1;i<=n;i++) a[i]=read();f[0][x]=1;g[0][x]=1;sort(a+1,a+1+n,cmp);for (int i=1;i<=n;i++){for (int j=0;j<=x;j++) f[i][j%a[i]]=max(f[i][j%a[i]],f[i-1][j]),g[i][j%a[i]]=(g[i][j%a[i]]+g[i-1][j])%mod;if (i!=n) for (int j=0;j<=x;j++) f[i][j]=max(f[i][j],f[i-1][j]),g[i][j]=(g[i][j]+g[i-1][j]%mod*(long long)(n-i)%mod)%mod; } for(int i=a[n];i>=0;i--){if (f[n][i]){cout<<i<<endl;cout<<g[n][i]<<endl;return 0;}}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/yimmortal/p/10160839.html

總結(jié)

以上是生活随笔為你收集整理的uoj22 外星人（dp）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。