admin 管理员组

文章数量: 1086866

印章、拿金币、数字游戏

目录

印章：

原题链接：

思路：

代码：

拿金币：

原题链接：

思路：

代码：

数字游戏：

原题链接：

思路：

代码：

印章：

原题链接：

“蓝桥杯”练习系统

思路：

明确dp[i][j]在使用中i、j、dp的含义，始终抓住这个含义，不要弄混，在这里我将i弄成物品种类，j弄成背包容量，dp为概率

代码：

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;const int N=25;
int n,m;
double p;
double dp[N][N];int main(){cin>>n>>m;p=1.0/n;dp[1][1]=1;for(int i=1;i<=n;i++){//物品种类for(int j=1;j<=m;j++){//背包容量if(i==1)dp[i][j]=pow(p,j-1);else if(i<=j)dp[i][j]=dp[i-1][j-1]*((n-i+1)*1.0/n)+dp[i][j-1]*(i*1.0/n);}}printf("%.4lf",dp[n][m]);system("pause");return 0;
}

拿金币：

原题链接：

“蓝桥杯”练习系统s

思路：

 在写本题时，切记不能用局部最优解，然后每到一个点，求它是从上面路径过来拿的金币多还是下面，递推公式这就出来了

代码：

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;const int N=1100;
int n;
int dp[N][N];int main(){cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)cin>>dp[i][j];}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dp[i][j]=max(dp[i][j-1],dp[i-1][j])+dp[i][j];}}cout<<dp[n][n];system("pause");return 0;
}

数字游戏：

原题链接：

“蓝桥杯”练习系统

思路：

深度遍历，利用回溯算法求解即可，注意第一次找到的即为最小字典序，找到直接返回，若没有满足则不输出，样例5即为找不到满足的条件，即不输出

代码：

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;const int N=15;
int n,sum;
bool vis[N];
int path[N],con[N];
bool flag;void dfs(int x,int u){if(u==n){for(int i=0;i<n;i++){con[i]=path[i];}for(int i=0;i<n-1;i++){for(int j=0;j<n;j++)con[j]+=con[j+1];}if(con[0]==sum){flag=1;}return ;}else {for(int i=1;i<=n;i++){if(flag)return ;if(vis[i]!=1){vis[i]=1;path[u]=i;dfs(i,u+1);vis[i]=0;}}}
}int main(){cin>>n>>sum;for(int i=1;i<=n;i++){if(flag)break;vis[i]=1;path[0]=i;dfs(i,1);vis[i]=0;}if(flag){for(int i=0;i<n;i++){cout<<path[i]<<' ';}}system("pause");return 0;
}

本文标签： 印章拿金币数字游戏

版权声明：本文标题：印章、拿金币、数字游戏 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1688026746a170381.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。