uoj22 外星人（dp）
题目大意：
给定一个\(n\)个数的序列\(a\)，给定一个\(x\)，其中\(a\)数组可以进行顺序的调换，每一个\(a_i\)都能使$x=x \mod a_i \(, 求最后经过一系列计算后的\)y\(，满足\)abs(x-y)$尽可能小，并求出方案数
QwQ 哇，一看到这个题。说实话，没什么好的思路。
也就发现了几个性质：
1.最后的\(y\)一定小于最小的\(a_i\)
2.如果存在一个\(a_i
那我们不妨将整个数组从大到小排序
先考虑第一问:
我们定义\(f[i][j]\)表示，考虑到第\(i\)个数，当前的值为\(j\)是否可行，首先我们令\(f[0][x]=1\)，然后对于当前的\(i\)，我们可以选择用它 ，也可以选择不用（换句话说，就是放一个比它更小的在前面，就可以实现不使用它了）但是后者需要满足\(i\ !=n\) 然后分别对应转移即可
这里有部分分的代码！
#include
#include
#include
#includeusing 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< 那么加上第二问呢，该怎么解决呢。
看了一些排列组合的题解，不过并不知道怎么做呀。倒是有一种更好理解的方法QwQ
我们令\(g[i][j]\)表示处理第\(i\)个数，当前值是\(j\)的方案数
如果我们使用这个点\(g[i][j \mod a_i ]+=g[i-1][j]\)（说明他待在当前的位置，且后面比他小的位置，都在他后面
如果不用\(g[i][j]=g[i-1][j]*(n-i)\) （表示他可以和他之后的任意一个比他小的数换位置，都不会使用这个点）（或者理解为他有\(n-i\)个空隙可以插进去
直接上代码
#include
#include
#include
#include
#includeusing 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< 转载于:https://www.cnblogs.com/yimmortal/p/10160839.html
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！