佛山服务类网站建设,注册网址步骤,临沂做网站找哪家好,用手机制作自己app软件下载P8597 [蓝桥杯 2013 省 B] 翻硬币
因为把相邻两个硬币翻转两次相当于不翻#xff0c;所以最优方案中同一组硬币最多只会翻转一次#xff0c;故翻转顺序无后效性#xff0c;考虑贪心#xff1a;从前往后比较#xff0c;发现一个不同的硬币就把它和他后面的硬币翻转#x…P8597 [蓝桥杯 2013 省 B] 翻硬币
因为把相邻两个硬币翻转两次相当于不翻所以最优方案中同一组硬币最多只会翻转一次故翻转顺序无后效性考虑贪心从前往后比较发现一个不同的硬币就把它和他后面的硬币翻转计数器累加这样最后累加结果一定是最优方案的次数。
#includebits/stdc.h
using namespace std;
char a[1009],b[1009];
int main(){scanf(%s,a);scanf(%s,b);int nstrlen(a);int cnt0;for(int i0;in;i){if(a[i]!b[i]){cnt;a[i]b[i];if(a[i1]o)a[i1]*;else a[i1]o;}}printf(%d,cnt);return 0;
}
P8637 [蓝桥杯 2016 省 B] 交换瓶子
和上面那道题有点类似都是交换这个也是贪心的思路
读入并遍历瓶子的序列如果该瓶子位置正确可以直接忽视如果不对答案加一往后扫扫到对应位置的瓶子就交换位置然后下一个瓶子继续
#includebits/stdc.h
using namespace std;
int a[10009];
int main(){int n;scanf(%d,n);for(int i1;in;i){scanf(%d,a[i]);}int ans0;for(int i1;in;i){if(a[i]!i){for(int ji;jn;j){if(a[j]i){int tempa[j];a[j]a[i];a[i]temp;ans;break;}}}}printf(%d,ans);return 0;
}
P1434 [SHOI2002] 滑雪
这题直接dfs会tle所以要采用记忆化搜索把每次搜到的点的结果记录下来下次再经过这个点时可以直接用上次搜到的结果可以省下许多时间
#includebits/stdc.h
using namespace std;
int maps[111][111],s[111][111],dx[4]{1,-1,0,0},dy[4]{0,0,1,-1};
bool use[111][111];
int n,m,cnt;
int dfs(int x,int y){if(s[x][y])return s[x][y];s[x][y]1;for(int i0;i4;i){int xxxdx[i],yyydy[i];if(xx0yy0xxnyymmaps[xx][yy]maps[x][y]){dfs(xx,yy);s[x][y]max(s[x][y],s[xx][yy]1);}}return s[x][y];
}
int main(){scanf(%d %d,n,m);for(int i1;in;i){for(int j1;jm;j){scanf(%d,maps[i][j]);}}for(int i1;in;i){for(int j1;jm;j){cntmax(cnt,dfs(i,j));}}printf(%d,cnt);return 0;
}
邻接矩阵介绍 邻接矩阵就是利用二维矩阵表示图中各顶点之间的关系对于有n个顶点的图来说用n阶方阵来表示该图其中矩阵元素表示从顶点到之间的边的大小表示边的权值。如果顶点到没有边则可以将设置为0或者。 如下图所示左边是一个无向图右边是其对应的邻接矩阵该图是无权图因此有边的值都设置为1。 下面是有向图及其邻接矩阵 从上面可见无向图的邻接矩阵是关于主轴对称的第i行或第j列就是顶点的度边数。图中的边数为1的个数/2。对于有向图由于其具有方向性因此邻接矩阵一般是不对称的第i行1的个数是顶点的出度第i列1的个数是其入度。图的边数等于矩阵中1的个数。
对于带权图来说只需要将1替换为边的权值即可下面是带权图及其邻接矩阵。 其中表示没有边可以是一个计算机能够接受的较大的值即可。
总结 图的邻接矩阵表示的优点 非常直观并且容易实现编写算法也较简便因而应用较广 根据矩阵元素Aij1或0便于判定两个顶点之间是否有边弧相连 计算顶点的度数或有向图的入度、出度方便 计算图的边数算法简单等。 图的邻接矩阵表示的缺点 邻接矩阵事实上是一种顺序存储结构具有顺序结构共有的缺点比如只能按最大空间需求申请内存空间、插入和删除顶点复杂等 空间复杂度高n个顶点的图存储邻接矩阵需要n2个单元如果一个图的顶点数较多但边弧数较少的话--稀疏图邻接矩阵一样需要n2个存储单元就太浪费存储空间 统计图的边数算法虽然简单用双重循环统计“1”的个数即可但其时间复杂度为O(n2)。
