这道题的难度为橙。
2025-04-16 12:44:39
发布于:广东
69阅读
0回复
0点赞
注:该解法不是正解,只在纯随机数据下适用。
我们充分发扬人类智慧。
走迷宫
由于是随机数据,所以注意到仅仅往左走或往下走一步后是最优解几乎是不可能的,因为它遍历的格子数较多。
所以我们可以只考虑往右,下走的情况。显然可以动态规划求解。
namespace Game1{
int dp[1005][1005];
int solve(){
memset(dp, 63, sizeof(dp));
dp[0][1] = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + a[i][j];//基础dp
}
}
return dp[n][m];
}
}
求最长回文子串长度
由于是随机数据,所以注意到即使是 01
串答案超过 也是极难做到的。
所以考虑枚举回文串对称轴位置,暴力走。
namespace Game2{
int solve(){
int ans = 0;
for(int i = 1; i <= t.size(); i++){
int l = i - 1, r = i + 1;//对称轴位置在 i
while(l >= 0 && r < t.size() && t[l] == t[r]) l--, r++;
ans = max(ans, r - l - 1);
l = i, r = i + 1;//对称轴位置在 i + 0.5
while(l >= 0 && r < t.size() && t[l] == t[r]) l--, r++;
ans = max(ans, r - l - 1);
}
return ans;
}
}
剩下的就很简单了,都是橙题思维橙题码量,所以本题应标橙(
全部评论 2
牛魔为什么乱搞我的数据
1周前 来自 北京
0下次出好点
1周前 来自 广东
0别用随机数据了
1周前 来自 广东
0
6
1周前 来自 江西
0
有帮助,赞一个