C++-蓝桥杯-波动数组[2014真题][DP优化]
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了C++-蓝桥杯-波动数组[2014真题][DP优化]，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1946字，纯文字阅读大概需要3分钟。
内容图文
无非是计算s1个+a和s2个-b的排列数（s1+s2=(1+n)*n/2=sum）
比如在第一位+a的话，之后的每个数都累积了+a，相当于当前排上了n-1个+a
所以，可以设状态f[i][j]为：用数字1~i(每个只能选一次)可以组成和为j的方案数
实际上就是一个容量=价值的01背包
对于s1（0~sum）：s=nx+s1*a-s2*b
即依次验证，对于每个s1，是否有：(s-s1*a+s2*b) %n==0
先看，70分代码，未进行空间优化的DP
1 #include <cstdio>
2 #include <iostream>
3 #include <algorithm>
4 using namespace std;
5 const int MOD=1e8+7,N=1010;
6 int f[N][100000],n,s,a,b,sum;
7 int DP(){
8 sum=(1+n)*n/2;
9 for(int i=0;i<=n;i++)f[i][0]=1;
10 for(int i=1;i<n;i++)
11 for(int j=1;j<=sum;j++){
12 if(i>j)f[i][j]=f[i-1][j];
13 else f[i][j]=f[i-1][j]+f[i-1][j-i];
14 f[i][j]%=MOD;
15 }
16 int ans=0;
17 for(int s1=0;s1<=sum;s1++){
18 int s2=sum-s1;
19 if((s-s1*a+s2*b)%n==0)ans=(ans+f[n-1][s1])%MOD;
20 }
21 return ans;
22 }
23 int main(){
24 cin>>n>>s>>a>>b;
25 cout<<DP()<<endl;
26 return 0;
27 }
问题就在于f数组的第二维，开不下了退而求其次只取到了1e5，实际上要到sum
由于转移是不跨行的，我们用滚动数组的方法，就可以进行DP的空间优化了，见100分代码
PS:对于需要检验的式子：(s-s1*a+s2*b) 是可能会爆int的,需要开ll，懒得写防爆乘了
1 #include <cstdio>
2 #include <iostream>
3 #include <algorithm>
4 using namespace std;
5 typedef long long ll;
6 const int MOD=1e8+7,N=600000;
7 int f[2][N],n,s,a,b,sum;
8 int DP(){
9 sum=(1+n)*n/2;
10 f[0][0]=f[1][0]=1;
11 for(int i=1;i<n;i++){
12 for(int j=1;j<=sum;j++)
13 if(i>j)f[1][j]=f[0][j];
14 else f[1][j]=(f[0][j]+f[0][j-i])%MOD;
15 for(int j=1;j<=sum;j++)swap(f[0][j],f[1][j]);
16 }
17 ll ans=0;
18 for(ll s1=0;s1<=sum;s1++){
19 ll s2=sum-s1;
20 if((s-s1*a+s2*b)%n==0)ans=(ans+f[0][s1])%MOD;
21 }
22 return ans;
23 }
24 int main(){
25 cin>>n>>s>>a>>b;
26 cout<<DP()<<endl;
27 return 0;
28 }
内容总结
以上是互联网集市为您收集整理的C++-蓝桥杯-波动数组[2014真题][DP优化]全部内容，希望文章能够帮你解决C++-蓝桥杯-波动数组[2014真题][DP优化]所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。