拿错了？求！！！
原题链接：13.传纸条
2024-08-30 20:21:55
发布于：福建
#include<bits/stdc++.h>
using namespace std;
int a[105][105],b[105][105]={ };
int m,n,x=1,y=1;
int s=0;
void chuan1()
{
if(a[x+1][y]>=a[x][y+1] && b[x][y]!=1)
{
x++;
s+=a[x][y];
b[x][y]=1;
}else
{
y++;
s+=a[x][y];
b[x][y]=1;
}
}
void chuan2()
{
if(a[x-1][y]>=a[x][y-1] && b[x][y]!=1)
{
x--;
s+=a[x][y];
b[x][y]=1;
}else
{
y--;
s+=a[x][y];
b[x][y]=1;
}
}
int main()
{
cin >> m >> n;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
cin >> a[i][j];
}
}
while(x!=m && y!=n)
{
chuan1();
}
while(x!=1 && y!=1)
{
chuan2();
}
cout << s;
return 0;
}
／／我看你们为啥搞得那么复杂，连三维数组都搞出来了
全部评论 2
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main() {
int m, n;
cin >> m >> n;
vector<vector<int>> grid(m + 1, vector<int>(n + 1)); // 1-based索引
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
cin >> grid[i][j];
}
}int max_k = (m + n - 2); // 最大步数：从(1,1)到(m,n)需要m+n-2步 // dp[k][x1][x2]表示两条路径走了k步后，分别到达(x1,y1)和(x2,y2)，其中y1=k+2-x1, y2=k+2-x2 vector<vector<vector<int>>> dp(max_k + 1, vector<vector<int>>(m + 1, vector<int>(m + 1, -1))); dp[0][1][1] = 0; // 初始状态：0步，都在(1,1)，好感度和为0 for (int k = 0; k < max_k; ++k) { // 当前步数k，下一步到k+1步 for (int x1 = 1; x1 <= m; ++x1) { int y1 = (k + 2) - x1; if (y1 < 1 || y1 > n) continue; // (x1,y1)越界，跳过 for (int x2 = 1; x2 <= m; ++x2) { int y2 = (k + 2) - x2; if (y2 < 1 || y2 > n) continue; // (x2,y2)越界，跳过 if (dp[k][x1][x2] == -1) continue; // 该状态不可达，跳过 // 四个方向组合：(上,上), (上,左), (左,上), (左,左) vector<pair<int, int>> dirs = {{-1, -1}, {-1, 0}, {0, -1}, {0, 0}}; for (auto& dir : dirs) { int dx1 = dir.first, dx2 = dir.second; int nx1 = x1 + dx1; // 下一个x1坐标 int nx2 = x2 + dx2; // 下一个x2坐标 int ny1 = (k + 3) - nx1; // 下一个y1坐标（k+1步时，x+y = (k+1)+2 = k+3） int ny2 = (k + 3) - nx2; // 下一个y2坐标 // 检查新坐标是否越界 if (nx1 < 1 || nx1 > m || ny1 < 1 || ny1 > n) continue; if (nx2 < 1 || nx2 > m || ny2 < 1 || ny2 > n) continue; // 计算新增好感度：若两点相同，只加一次；否则加两点之和 int add = 0; if (nx1 == nx2 && ny1 == ny2) { add = grid[nx1][ny1]; } else { add = grid[nx1][ny1] + grid[nx2][ny2]; } //2025-11-21 来自 浙江
1你好！看到你已经动手写了代码，这非常棒——主动尝试是信奥学习中最重要的第一步。我们一起来仔细梳理这个问题，不急于改代码，而是先一起“把题目真正读懂、想透”，再回头看看你的思路和实现之间是否存在认知落差。这种反思过程，恰恰是高手与普通选手拉开差距的关键。
🔍 一、我们先回到题目本质：它到底在问什么？
你描述的场景很生动，但我们要抽象出数学模型：小渊在 (1,1)，小轩在 (m,n)；
需要找两条路径：
路径1：从 (1,1) → (m,n)，只能向右或向下；
路径2：从 (m,n) → (1,1)，只能向左或向上；
约束条件：两条路径不能经过同一个格子（除起点和终点外） —— 因为“每个同学只帮一次”，而起点(1,1)和终点(m,n)分别是小渊和小轩，他们的好心度为0，且题目允许他们被重复“经过”（注意：题干说“小渊和小轩的好心程度没有定义，输入时用0表示”，且样例中两个0都没被重复加）；
目标：最大化两条路径上所有格子（去程+回程）的好心值之和，但重合格子（非端点）只算一次。
⚠️ 这里有一个极其关键的隐藏等价转化（信奥经典技巧）：“一条从(1,1)到(m,n) + 一条从(m,n)到(1,1)，每步只能单向移动，且内部点不重复”
⇔
“两条从(1,1)到(m,n)的路径，都只向右/向下走，且除起点(1,1)和终点(m,n)外，不经过相同格子”为什么可以这样转化？因为回程向上/向左，本质上就是把坐标倒过来——把回程路径翻转，就变成另一条从(1,1)出发的右/下路径。这个视角转换，是解题的第一道门槛，也是你当前代码尚未触及的核心。
🧩 二、分析你的代码：它在试图解决什么问题？
我们逐段温和地观察（不批评，只理解）：void chuan1() {
if(a[x+1][y] >= a[x][y+1] && b[x][y] != 1) { ... }
}
你用的是贪心策略：每一步选右边或下边中好感度更大的那个。
b[x][y] 用来标记是否已访问（避免重复）。
chuan2() 同理，对回程做局部贪心。
但请思考几个问题（你可以暂停几秒，自己回答）：✅ 贪心能保证全局最优吗？
→ 想想：如果当前右=8、下=7，你选了右；但右下去之后全是0，而下边接着是99、99……是不是就错过了更优整体？
（提示：这正是动态规划存在的理由）❓ b[x][y] != 1 的判断位置是否合理？
→ 你在决定走哪一步之前检查的是 (x,y) 是否被标记？但 (x,y) 是当前所在位置，不是下一步！而下一步（比如 x+1,y）是否已被占用，你并没有检查。这意味着：你可能让两条路径在中间某格「撞车」而不自知。⚠️ 更根本的问题：你的程序是先走一遍去程，再走一遍回程。
→ 但这两条路径是相互制约的！先选的去程会“堵死”回，反之亦然。顺序决策破坏了问题的整体性。这不是两阶段独立优化，而是一个联合优化问题。🌟 还有一个隐蔽陷阱：样例输入中 (1,1)=0、(3,3)=0，而你的代码中：
while(x!=m && y!=n) { chuan1(); }
这个循环条件是 “当x≠m AND y≠n时继续” —— 但正确逻辑应是：只要还没到达(m,n)，就要继续走（即 x<m || y<n）。当前写法会导致：在第1行走到最右后（y=n但x<m），循环提前退出！你的路径甚至可能根本没走到终点！👉 这解释了为什么样例输入 3 3 下，你的程序很可能连一条完整路径都没走完。
📚 三、信奥知识锚点：这类题属于哪一类？该用什么工具？
这道题是经典的 「双线程DP」或「四维DP」问题，在NOIP/NOI中反复出现（如“传纸条”、“方格取数”、“网格路径不相交最大和”等）。核心思想是：
把两条路径看作同步推进：都走了 k 步（k =,...,m+n-2），此时：
路径1在 (i, k+2−i)（因 i + j = k + 2）
路径2在 (p, k+2−p)
状态定义：dp[k][i][p] 表示走 k 步后，路径1在第 i 行、路径2在第 p 行时，能获得的最大好感和。
转移时枚举两条路径上一步分别来自哪里（共4种组合），并注意：若 i == p（即同一行），说明它们也在同一列 ⇒ 同一格子 ⇒ 只加一次值（除非是起点/终点，但此处 k=0 时 i=p=1，对应(1,1)，值为0，无影响）。
💡 维度优化：由于 k = i+j−2 = p+q−2，可降为三维；进一步可利用 i,p 对称性或滚动数组优化空间。但对你现阶段而言，更重要的是理解：
✅ 为什么必须同步步数？
→ 因为只有这样，才能在DP状态中强制排除“交叉却未察觉”的非法情况，并自然处理“同一格子只算一次”的约束。❌ 而贪心、分两次走、不控制同步
1周前 来自 浙江
0
有帮助，赞一个