字母收集

NC221826. 字母收集

描述

有一个 $n*m$ 的矩形方阵，每个格子上面写了一个小写字母。
小红站在矩形的左上角，她每次可以向右或者向下走，走到某个格子上就可以收集这个格子的字母。
小红非常喜欢 "love" 这四个字母。她拿到一个 l 字母可以得 4 分，拿到一个 o 字母可以得 3 分，拿到一个 v 字母可以得 2 分，拿到一个 e 字母可以得 1 分。
她想知道，在最优的选择一条路径的情况下，她最多能获取多少分？

输入描述


接下来的  行 每行一个长度为  的、仅有小写字母构成的字符串，代表矩形方阵。

输出描述

小红最大可能的得分。

示例1

输入:

3 2
ab
cd
ef

输出:

说明:

选择下、下、右）这条路径即可，可以收集到 acef 这四个字母各一次，获得 0+0+1+0=1 分。

示例2

输入:

2 3
lle
ove

输出:

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 16ms, 内存消耗: 2852K, 提交时间: 2021-09-11 14:21:51

#include<bits/stdc++.h>
using namespace std;
char mp[1000][1000];
int dp[1000][1000];
map<char,int> ma;

int main(){
	ma['l']=4;
	ma['o']=3;
	ma['v']=2;
	ma['e']=1;
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			cin>>mp[i][j];
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			dp[i][j]=max(dp[i-1][j],dp[i][j-1])+ma[mp[i][j]];
		}
	}
	cout<<dp[n][m]<<endl;
}

上一题

下一题

详情