题目链接：https://ac.nowcoder.com/acm/contest/102742/D
1、假如去掉墙这个限制条件，那么本题就变成了经典的线性dp问题，显然令dp[i,j]表示从原点走到(i,j)能得到的最大价值。dp状态转移方程为dp[i][j]=max(dp[i-1],dp[i][j
展开全文
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10,INF=1e9;
int n,m,a[N][N];
int g[N][N],dp[N][N];//dp[i][j] 记录在（i，j）位置的最大money
展开全文
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const long long INF = 1e18;
int main() {
ios_
展开全文
1. 问题分析
本题是一个典型的带有动态约束的网格路径最优化问题。其核心特征在于：
移动限制：仅能向右或向下，构成了典型的有向无环图（DAG）结构。
时空约束：方格变为障碍点（墙）的时间 是动态的。这意味着一个方格是否可行，不仅取决于其坐标 ，还取决于到达该方格的时间步。
即时判定：每一回合先发
展开全文
对于不可达的(i,j)我们进行标记，它即无法传递给右边的，也或者是下边的 在这种情况下进行dp 找出所有非标记点中最大的金币数就是答案
void solve() {
int n,m;
cin>>n>>m;
//创建mat,lmat记录金币和不可抵
展开全文
// #include<bits/stdc++.h>
// using namespace std;
// #define int long long
// int n,m;
// int w[1010][1010];
// int st[1010][1010];
// int f[10
展开全文
import sys
# 定义极大值
INF = 0x3f3f3f3f
def kkk():
# 读取输入
input_data = sys.stdin.read().split()
ptr = 0
# 读取行列数（n行m列）
n = int(in
展开全文
题目链接
收集金币
题目描述
在一个 的网格迷宫中，每个方格 都有一定数量的金币。小K从左上角 出发，每回合只能向右或向下移动一格。
迷宫中存在动态障碍：已知有 条信息，每条信息形如 ，表示方格 会在第 回合开始时永久变成墙。
小K的目标是规划一条路径，使得收集到的金币总数最多。一个方格
展开全文
#include<bits/stdc++.h>
using namespace std;
int inn[1005][1005];
#define int long long //这题没想到要开长整型弄半天
void solve() {
int n,m;cin>>n
展开全文
题目链接
网格迷宫
题目描述
在一个 的网格迷宫中，每个方格 都有一定数量的金币。小K从左上角 出发，每回合只能向右或向下移动一格。有 条信息，每条信息表示方格 会在第 回合变成永久的墙。小K在第 回合移动时，会先等所有该回合的墙出现后，再进行移动决策。你需要计算小K最多能收集到多少金
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
