php制作网站用什么软件,企业解决方案能力介绍,自建房设计图,山东手机响应式网站建设设计话不多说#xff0c;直接看题#xff1a; 我们不妨把问题抽象一下#xff1a;
首先#xff0c;我们由裴蜀定理知道如果两个数互质#xff0c;那么axbyc一定有整数解#xff08;只要c为1的倍数也就是整数#xff09;#xff0c;因此问题就转换为求选一些数使他们gcd1直接看题 我们不妨把问题抽象一下
首先我们由裴蜀定理知道如果两个数互质那么axbyc一定有整数解只要c为1的倍数也就是整数因此问题就转换为求选一些数使他们gcd1对1特判
考虑到与背包问题的类似性于是我们令f[i][j]为前i个数gcdj的最小花费。
于是我们得到转移方程f[i][j]min(f[i-1][j],f[i-1][k]c[i])(k与li的gcdj)
但是我们注意一下范围k显然不能遍历到10^9,注意到我们遍历的为gcd,而这个远小于li,因此我们可以用map来优化空间存可能的gcd),每一轮的gcd在循环时直接推出即可。
下面为AC代码
#includebits/stdc.h
using namespace std;
#define ma 10000000
#define int long long
int n,l[310],c[310],cnt;
mapint,int a[310];
int _gcd(int a,int b){while(b){int tmpb;ba%b;atmp;}return a;
}
struct node{int dian,zhi;
};
queueint q;
signed main(){cinn;for(int i1;in;i) scanf(%lld,l[i]);for(int i1;in;i) scanf(%d,c[i]);int ansma;for(int i1;in;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]]);mapint,int::iterator it;for(ita[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(ita[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) ansmin(ans,a[i][1]);}if(ansma) cout-1;else coutans;
}
接题 我们直接令f[i][j]表示到i的位置时所跳的距离j时得到的最大值。
转移方程为
f[i][j]p[i]max(f[i-j][j],f[i-j][j-1],f[i-j][j1]).
但是当d30000时空间就不够了。
我们不妨计算1...n30000,发现最大的波动范围最多-250--250
因此我们不妨让j的位置存波动值即可。注意判断范围
下面是AC代码
#includebits/stdc.h
using namespace std;
#define ck 250
int n,d,dp[30001][502],a[30010],x,max1;
int main(){cinnd;for(int i1;in;i){scanf(%d,x);a[x];max1max(x,max1);}memset(dp,-0x3f,sizeof(dp));dp[d][ck]a[d];int ansa[d];for(int i1d;imax1;i){for(int j0;j500;j){int x1dj-ck;if(i-x10) continue;if(x10) continue;for(int k-1;k1;k){if(jk0) dp[i][j]max(dp[i][j],dp[i-x1][jk]a[i]);}ansmax(ans,dp[i][j]);}}coutans;
}
