欢迎来到天天文库
浏览记录
ID:56766628
大小:297.50 KB
页数:55页
时间:2020-07-08
《蓝桥杯分类模拟题.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、#本资料非原创,为了方便大家复习,特此整理。在此感谢提供试题的作者专题一:动态规划1.结点选择问题描述有一棵n个节点的树,树上每个节点都有一个正整数权值。如果一个点被选择了,那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少?解题思路:这题模型是树形动态规划入门题目,dp[i][0]表示该节点不被选择,dp[i][1]表示该结点被选择。转移方程为:dp[u][1]+=dp[v][0];//选择了u结点,则与它邻接的结点不选;dp[u][0]+=max(dp[v][0],dp[v][1]);不选择u结点,则与
2、它邻接的结点选择结果最大的;应该特别注意:该题结点数量较大,应该选用邻接表存储边的关系1.#include 2.#include 3.#define max(a,b) ((a)>(b)?(a):(b)) 4.#define maxn 5.bool vis[maxn]; 6.int dp[maxn][2]; 7.int father[maxn]; 8.int head[maxn]; 9.int n; 10.int cnt; 11.struct Edge 12.{
3、13. int to,next; 14.}edge[2*maxn]; 15.void add(int u,int v) 16.{ 17. edge[cnt].to=v; 18. edge[cnt].next=head[u]; 19. head[u]=cnt++; 20.} 21.void treedp(int u) 22.{ 23. vis[u]=1; 24. for(int i=head[u];i!=-1;i=edge[i].next) 25. { 2
4、6. int v=edge[i].to; 1. if(!vis[v]) 2. { 3. treedp(v); 4. dp[u][1]+=dp[v][0]; 5. dp[u][0]+=max(dp[v][1],dp[v][0]); 6. } 7. } 8.} 9.void init() 10.{ 11. cnt=0; 12. memset(dp,0,sizeof
5、(dp)); 13. memset(father,0,sizeof(father)); 14. memset(vis,0,sizeof(vis)); 15. memset(head,-1,sizeof(head)); 16.} 17.int main() 18.{ 19. init(); 20. scanf("%d",&n); 21. for(int i=1;i<=n;i++) 22. scanf("%d",&dp[i][1]); 23. int ro
6、ot=0; 24. int begin=1; 25. for(int i=0;i7、8、begin) 33. { 34. root=a; 359、. } 36. } 37. 38. while(father[root]) 39. root=father[root]; 40. treedp(root); 41. int ans; 42. ans=max(dp[root][0],dp[root][1]); 43. printf("%d",ans); 44.} 2.K好数 问题描述如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字,那么我们就说这个数是K好数。求L位K进制10、数中K好数的数目。例如K=4,L=2的时候,所有K好数为11、13、20、22、30、31、33共7个。由于这个数目很大,请你输出它对取模后的值。解题思路:dp[i][j]表示第i位为j的时候的个I好数个数;因此有转移方程:dp[i][j]=dp[i-1][m]+dp[i][j];m为上一位的值,满足的条件应为m-j
7、
8、begin) 33. { 34. root=a; 35
9、. } 36. } 37. 38. while(father[root]) 39. root=father[root]; 40. treedp(root); 41. int ans; 42. ans=max(dp[root][0],dp[root][1]); 43. printf("%d",ans); 44.} 2.K好数 问题描述如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字,那么我们就说这个数是K好数。求L位K进制
10、数中K好数的数目。例如K=4,L=2的时候,所有K好数为11、13、20、22、30、31、33共7个。由于这个数目很大,请你输出它对取模后的值。解题思路:dp[i][j]表示第i位为j的时候的个I好数个数;因此有转移方程:dp[i][j]=dp[i-1][m]+dp[i][j];m为上一位的值,满足的条件应为m-j
此文档下载收益归作者所有