题源洛谷
1.P1765 手机
一般的手机的键盘如左图所示，要按出英文字母就必须要按数字键多下。例如要按出?x?就得按 9 两下，第一下会出?w，而第二下会把?w?变成?x。0 键按一下会出一个空格。
?
你的任务是读取若干句只包含英文小写字母和空格的句子，求出要在手机上打出这个句子至少需要按多少下键盘。
输入格式
一行句子，只包含英文小写字母和空格，且不超过 200 个字符。
输出格式
一行一个整数，表示按键盘的总次数。
输入输出样例
输入
i have a dream
输出
23【题解】
#include<iostream>
#include<cstring>
using namespace std;
int a[30]={1,2,3, 1,2,3, 1,2,3, 1,2,3, 1,2,3, 1,2,3,4, 1,2,3, 1,2,3,4};//每个字母所需要按的次数
int main(){
string str;
int ans = 0; //记录最后需要按多少次键盘
getline(cin, str); //读入一行字符
for(int i = 0; i < str.size(); i ++){
if(str[i] == ' ') ans ++; //读到空格
if(str[i] >= 'a' && str[i] <= 'z') ans += a[str[i] - 'a'];
}
cout<<ans;
return 0;
}2.?P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles
观察下面的数字金字塔。
写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5 在上面的样例中,从7→3→8→7→5?的路径产生了最大。
输入格式
第一个行一个正整数?rr?,表示行的数目。
后面每行为这个数字金字塔特定行包含的整数。
输出格式
单独的一行,包含那个可能得到的最大的和。
输入输出样例
输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出
30【题解】
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int a[N][N];
int main(){
int n;
cin>>n;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= i; j ++) cin>>a[i][j];
for(int i = n - 1; i >= 1; i --)
for(int j = 1; j <= i; j ++){
a[i][j] = max(a[i + 1][j], a[i + 1][j + 1]) + a[i][j];
}//从下往上加
cout<<a[1][1];
return 0;
}