话不多说，直接看题：
我们不妨把问题抽象一下：
首先，我们由裴蜀定理知道如果两个数互质，那么ax+by=c一定有整数解（只要c为1的倍数也就是整数），因此问题就转换为求选一些数使他们gcd==1（对1特判）
考虑到与背包问题的类似性，于是我们令f[i][j]为前i个数gcd==j的最小花费。
于是我们得到转移方程：f[i][j]=min(f[i-1][j],f[i-1][k]+c[i])(k与li的gcd==j)
但是我们注意一下范围k显然不能遍历到10^9,注意到我们遍历的为gcd,而这个远小于li,因此我们可以用map来优化空间（存可能的gcd),每一轮的gcd在循环时直接推出即可。
下面为AC代码：
#include<bits/stdc++.h>
using namespace std;
#define ma 10000000
#define int long long
int n,l[310],c[310],cnt;
map<int,int> a[310];
int _gcd(int a,int b){
while(b){
int tmp=b;
b=a%b;
a=tmp;
}
return a;
}
struct node{
int dian,zhi;
};
queue<int> q;
signed main(){
cin>>n;
for(int i=1;i<=n;i++) scanf("%lld",&l[i]);
for(int i=1;i<=n;i++) scanf("%d",&c[i]);
int ans=ma;
for(int i=1;i<=n;i++){
if(a[i].count(l[i])==0) a[i][l[i]]=c[i];
else a[i][l[i]]=min(c[i],a[i][l[i]]);
map<int,int>::iterator it;
for(it=a[i-1].begin();it!=a[i-1].end();it++){
if(a[i].count(it->first)==0) a[i][it->first]=a[i-1][it->first];
else a[i][it->first]=min(a[i-1][it->first],a[i][it->first]);
}
for(it=a[i-1].begin();it!=a[i-1].end();it++){
if(a[i].count(_gcd(it->first,l[i]))==0) a[i][_gcd(it->first,l[i])]=a[i-1][it->first]+c[i];
else a[i][_gcd(it->first,l[i])]=min(a[i-1][it->first]+c[i],a[i][_gcd(it->first,l[i])]);
}
if(a[i].count(1)!=0) ans=min(ans,a[i][1]);
}
if(ans>=ma) cout<<-1;
else cout<<ans;
} 接题：
我们直接令f[i][j]表示到i的位置时所跳的距离j时得到的最大值。
转移方程为：
f[i][j]=p[i]+max(f[i-j][j],f[i-j][j-1],f[i-j][j+1]).
但是当d=30000时空间就不够了。
我们不妨计算1+...+n<=30000,发现最大的波动范围最多（-250--250）
因此，我们不妨让j的位置存波动值即可。（注意判断范围）
下面是AC代码：
#include<bits/stdc++.h>
using namespace std;
#define ck 250
int n,d,dp[30001][502],a[30010],x,max1;
int main(){
cin>>n>>d;
for(int i=1;i<=n;i++){
scanf("%d",&x);
a[x]++;
max1=max(x,max1);
}
memset(dp,-0x3f,sizeof(dp));
dp[d][ck]=a[d];
int ans=a[d];
for(int i=1+d;i<=max1;i++){
for(int j=0;j<=500;j++){
int x1=d+j-ck;
if(i-x1<=0) continue;
if(x1<=0) continue;
for(int k=-1;k<=1;k++){
if(j+k>0) dp[i][j]=max(dp[i][j],dp[i-x1][j+k]+a[i]);
}
ans=max(ans,dp[i][j]);
}
}
cout<<ans;
}
