数组三角形

题目描述

上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。

路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右 边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。

输入描述

输入的第一行包含一个整数 (1≤N≤100)N (1≤N≤100)，表示三角形的行数。

下面的 N 行给出数字三角形。数字三角形上的数都是 0 至 100 之间的整数。

输出描述

输出一个整数，表示答案。

输入输出样例

示例

输入

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

输出

27

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

题解：

        1.这个题目最开始想的就是dfs算法，但是超时了，后来就想到了多态规划的题目。

         2.但是这里有一个要注意的点就是向左下走的次数与向右下走的次数相差不能超过 1，通过纸上模拟，可以得出是偶数行的时候，有两个值可能是最大值，是奇数行的时候，有一个值是最大值。不管是偶数行还是奇数行，最大值都是在行中间的位置。

#include<iostream>
#include<math.h>
using namespace std;
int n,m[109][109],t[109][109];
int main() {cin>>n;for(int i=1; i<=n; i++) {for(int j=1; j<=i; j++) {cin>>m[i][j];}}t[1][1]=m[1][1];for(int i=2;i<=n;i++){for(int j=1;j<=i;j++){t[i][j]=max(t[i-1][j],t[i-1][j-1])+m[i][j];}}if(n%2==0){//偶数行cout<<max(t[n][(n+1)/2],t[n][(n+2)/2]);}else{//奇数行cout<<t[n][(n+1)/2];    }return 0;
}

 排序

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

小蓝最近学习了一些排序算法，其中冒泡排序让他印象深刻。

在冒泡排序中，每次只能交换相邻的两个元素。

小蓝发现，如果对一个字符串中的字符排序，只允许交换相邻的两个字符， 则在所有可能的排序方案中，冒泡排序的总交换次数是最少的。

例如，对于字符串 lan 排序，只需要 1 次交换。对于字符串 qiao 排序，总共需要 4 次交换。

小蓝找到了很多字符串试图排序，他恰巧碰到一个字符串，需要 100100 次交 换，可是他忘了吧这个字符串记下来，现在找不到了。

请帮助小蓝找一个只包含小写英文字母且没有字母重复出现的字符串，对 该串的字符排序，正好需要 100100 次交换。如果可能找到多个，请告诉小蓝最短的那个。如果最短的仍然有多个，请告诉小蓝字典序最小的那个。

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

 题解：

        1.冒泡排序的n个数最多的排序次数是n*(n-1)/2次，通过计算n最小值为15,15*14=105；

        2.105-100=5，只需把第6个字母往后移到第1位即可，即jonmlkihgfedcba。

#include<iostream>
#include<math.h>
#include<string.h>
using namespace std;
int main() {cout<<"jonmlkihgfedcba";return 0;
}

跑步锻炼

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

小蓝每天都锻炼身体。

正常情况下，小蓝每天跑 11 千米。如果某天是周一或者月初（11 日），为了激励自己，小蓝要跑 22 千米。如果同时是周一或月初，小蓝也是跑 22 千米。

小蓝跑步已经坚持了很长时间，从 20002000 年 11 月 11 日周六（含）到 20202020 年 1010 月 11 日周四（含）。请问这段时间小蓝总共跑步多少千米？

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

代码

#include<iostream>
#include<math.h>
#include<string.h>
using namespace std;
int mouth[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int main() {int day=5,sign=0,sum=0;for(int i=2000;i<=2020;i++){//闰年的处理 if((i%4==0&&i%100!=0)||(i%400==0)){mouth[2]=29;}else{mouth[2]=28;}int t = i!=2020? 12: 10;for(int j=1;j<=t;j++){for(int k=1;k<=mouth[j];k++){if(i==2020&&j==10&&k==2){sign=1;break;}day++;sum+=1;if(k==1){//判断是不是月初sum+=1;}if(day==8){//判断是不是星期一day=1;if(k!=1){sum+=1;}}}if(sign==1)break;} if(sign==1)break;} cout<<sum;return 0;
}