09-07 18:49 南昌大学 Java 发布于广东
关注
9月7日滴滴笔试AK
## 选择题
略
## 编程题
### T1 最大美观度（100%）
三种情况，一个格子、两个格子、三个或以上格子，时间复杂度O（1）
### T2 字符消除（100%）
考虑记忆化搜索代替dp，先是挨着删除，比如abcdef，删除ab，求cdef，删除cd，求abef。这样过27%，因为重复太多，比如ab删除了，后面求cdef又删除cd，和第一次循环删除cd效果相同。
考虑不可逆的记忆化，删除第一个字符和其他（1+2i）位置的字符，保证子串是偶数，AC。
#pragma GCC optimize(3)
#include
#include
using namespace std;
typedef long long ll;
unordered_map mp;
int a[27][27];
int n, k;
string s;
ll dfs(string str){
string key = str;
if(str == "") return 0;
if(mp.find(key) != mp.end()) return mp[key];
ll res = 0;
for(int i = 1; i < str.size()-1; i+=2) res = max(res, dfs(str.substr(1, i) + str.substr(i + 1)) + a[(str[0] - 'a')][(str[i] - 'a')]);
return mp[key] = res;
}
int main(){
cin >> n >> k;
for(int i = 0; i < k; i++) for(int j = 0; j < k; j++) cin >> a[i][j];
cin >> s;
dfs(s);
cout << mp[s];
return 0;
}
略
## 编程题
### T1 最大美观度（100%）
三种情况，一个格子、两个格子、三个或以上格子，时间复杂度O（1）
### T2 字符消除（100%）
考虑记忆化搜索代替dp，先是挨着删除，比如abcdef，删除ab，求cdef，删除cd，求abef。这样过27%，因为重复太多，比如ab删除了，后面求cdef又删除cd，和第一次循环删除cd效果相同。
考虑不可逆的记忆化，删除第一个字符和其他（1+2i）位置的字符，保证子串是偶数，AC。
#pragma GCC optimize(3)
#include
#include
using namespace std;
typedef long long ll;
unordered_map
int a[27][27];
int n, k;
string s;
ll dfs(string str){
string key = str;
if(str == "") return 0;
if(mp.find(key) != mp.end()) return mp[key];
ll res = 0;
for(int i = 1; i < str.size()-1; i+=2) res = max(res, dfs(str.substr(1, i) + str.substr(i + 1)) + a[(str[0] - 'a')][(str[i] - 'a')]);
return mp[key] = res;
}
int main(){
cin >> n >> k;
for(int i = 0; i < k; i++) for(int j = 0; j < k; j++) cin >> a[i][j];
cin >> s;
dfs(s);
cout << mp[s];
return 0;
}
全部评论
几只小松鼠
蚌埠坦克学院 Java
😭😭
王鹏的好室友
中国石油大学（华东） Java
佬太强了
在游泳的00后很漂亮
北京航空航天大学 C++
请问为什么dfs的时候，为什么要用begin和i来合并，可以用i和i+1来合并吗
讲原则的驼瑞驰在吃瓜
门头沟学院 Java
佬约面了吗
相关推荐
点赞 评论 收藏
分享