[NOI Online 2021 入门组] 吃豆人

首先，这个方法是错的，但是官方数据满分，洛谷95，正解看官方

洛谷的传送门

由画图我们可以轻易得到，如果最上面一个豆确定，那么这个路径是唯一的。

这样想的话，我们不妨枚举从最上面一行的每个起点出发，计算所有可以走的路径，而除了最高行和最低行以外每行可以吃到两颗豆。（斜对角走法除外），然后再算出斜对角能吃的豆，找到最优的路径标记其最高点，然后再跑一边把这些位置的$flag$全部设成$0$表示这里的豆吃过了，然后再执行一次这样的操作找到第二遍的最优路径。

有那么亿点贪心的思想在其中吧。

在吃没横行的两颗豆时我们可以直接计算$+$上两颗豆的价值是多少，而并非傻傻地真的模拟一边，这样的话时间复杂度应该是 O ( 2 × n 2 ) O(2×n^2) O(2×n2)，数据规模最大$1000$，显然是可行的。

而特意做的一遍$flag$其实是不浪费多少时间的。

Code

#include
using namespace std;
int maxx,a[1010][1010],n,biaoji,qidian,ans,daan,zuoxie,youxie;
bool flag[1010][1010];
void work()
{int sum=a[1][2]+a[2][1]+a[2][3]+a[3

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！