@[598xhy](/user/700986) 这个题贪心思路本来就不对：比如你先走一个比较大的数，结果在其后面的数字都很小。
by MarchKid_J0e @ 2023-01-05 17:35:34
@[598xhy](/user/700986) 而且路径清空也是错误的
by MarchKid_J0e @ 2023-01-05 17:36:22
這個題貪心思路本來就不對：比如你先走一個比較大的數，結果在其後面的數字都很小。
by MarchKid_J0e @ 2023-01-05 17:38:24
而且路徑清空也是錯誤的(雖然不知道為什麽是繁體中文)
by MarchKid_J0e @ 2023-01-05 17:39:04
@[MarchKid_J0e](/user/760799) 可是我走的是每一個格子都對比，類似於金字方陣的貪心啊~~而且樣例最後還多出來一個5，輸出72~~
by IronRoosterIkun @ 2023-01-06 07:56:17
@[598xhy](/user/700986) 你的思路應該是每次從上邊和左邊較大值轉移吧。然後清空路徑，再貪心一次。先不管思路正確性。按照你這個思路，清空路徑就是錯誤的：不應該先把路徑復製一遍到當前節點嗎？代碼裏標出來了。
```cpp
#include<cstdio>
#include<utility>
#include<cstring>
using namespace std;
#define mkpr(a,b) make_pair(a,b)
int n,x,y;long long a[11][11],z,ans;
struct Build_Map//建圖
{
pair<int,int> odr[20];//已經走過的順序
long long val;//價值
int rp=1;//處理目前數組儲存的順序
}mp[11][11];
long long fw()//貪心訪問
{
for(int i=2;i<=n;i++)
{
for(int j=2;j<=n;j++)
{
if(mp[i-1][j].val>mp[i][j-1].val)
{
mp[i][j] = mp[i - 1][j]; //复制
mp[i][j].val=a[i][j]+mp[i-1][j].val;
mp[i][j].odr[mp[i][j].rp++]=mkpr(i-1,j);
}
else
{
mp[i][j] = mp[i][j - 1];// 复制
mp[i][j].val=a[i][j]+mp[i][j-1].val;
mp[i][j].odr[mp[i][j].rp++]=mkpr(i,j-1);
}
//貪心思想
}
}
// for (int i = 1; i <= n; i++, putchar('\n'))
// for (int j = 1; j <= n; j++, putchar(' '))
// printf("%d", mp[i][j].val);
return mp[n][n].val;
}
void cllg()//處理路過的方塊
{
for(int i=1;i<=2*n;i++)
a[mp[n][n].odr[i].first][mp[n][n].odr[i].second]=0;
}
int main()
{
scanf("%d",&n);
while(scanf("%d%d%lld",&x,&y,&z)&&(x||y||z))a[x][y]=z;
ans=fw();
cllg();
memset(mp,0,sizeof mp);
ans+=fw();
printf("%lld",ans);
return 0;
}
```
可以過樣例，但是思路不對，還是那樣的：
這個題貪心思路本來就不對：比如你先走一個比較大的數，結果在其後面的數字都很小。
by MarchKid_J0e @ 2023-01-06 08:28:20
@[598xhy](/user/700986) 比如這組數據，你的答案是 $12$，正確答案 $30$，建議換成 dp 做法~~或者網絡流~~。
Input:
```
3
1 1 10
1 3 5
2 2 6
2 3 4
3 1 8
3 2 2
0 0 0
```
Output:
```
30
```
by MarchKid_J0e @ 2023-01-06 08:32:07
@[MarchKid_J0e](/user/760799) 懂了，感謝指點
by IronRoosterIkun @ 2023-01-06 08:32:24
貪心的答案顯然偏小。
by MarchKid_J0e @ 2023-01-06 08:32:38