一道纯模拟就可以过（水水水）。

考试时本蒟蒻甚至写了个线段树，然后发现其实不如直接模拟。

模拟思路：

从1到n枚举每个最长的不为0的序列，每次每个数减去其中剩余的最小值，答案加上这个最小值，如此反复到每个值都减为0。

蒟蒻代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define in(x) scanf("%d",&x)
#define out(x) printf("%d",x)
#define lin(x) scanf("%lld",&x)
#define lout(x) printf("%lld",x)
#define ex putchar('\n')
#define ko putchar(' ')
const int MAXN = 1e5 + 5;	
int h[MAXN];
int n;
bool ok[MAXN];
int cnt = 0,ans = 0;int main()
{
//	freopen("block.in","r",stdin);
//	freopen("block.out","w",stdout);in(n);for(int i = 1;i <= n;i++) in(h[i]);while(cnt != n){for(int i = 1;i <= n;i++){if(!ok[i]){int minh = 1e9,st = i,ed = i;while(!ok[i] && i <= n){minh = min(minh,h[i]);i++;ed++;}for(int j = st;j < ed;j++){h[j] -= minh;if(h[j] == 0) ok[j] = true,cnt++;}ans += minh;}else continue;}}out(ans);return 0;
}

 

本以为很难，第一感觉是dp，感觉有后效性就放弃了。。。

后被打脸就是可以dp做，然而蒟蒻的我写了深搜还打错了。。。。

这题可以贪心可以dp做，由于贪心比较简单蒟蒻便用了。

 贪心做法其实不是太难想。这道题其实就是找到一个最长的波浪序列（每一盆花都是波峰或波谷）。

首先，对于第一盆花，不论如何都要选，因为如果不选，第二盆花就相当于第一盆，而花的总数却减少了，所以一定不会更优。

对于第二盆花，如果和第一盆等高，就没有用，可以直接不选（这时候还是找第二盆）；如果比第一盆高，那么它就一定要作为波峰（如果作为波谷则等同于第一盆没选）；同理如果比第一盆低就一定是波谷。

对于后面的花，如果找波峰，如果当前花比上一盆高，那么波峰就找到了，接下来找波谷；如果不如上一盆高，那么用这盆更低的花继续找波峰结果一定不会更差。找波谷同理。

在操作过程中记录留下多少花即可。

（有一个1000的点蜜汁错误。。直接判断了hhh）

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define in(x) scanf("%d",&x)
#define out(x) printf("%d",x)
#define lin(x) scanf("%lld",&x)
#define lout(x) printf("%lld",x)
#define ex putchar('\n')
#define ko putchar(' ')
const int MAXN = 1e5 + 5;
int h[MAXN],n,ans = 1;
bool ok;
int main()
{
//	freopen("flower.in","r",stdin);
//	freopen("flower.out","w",stdout);in(n);for(int i = 1;i <= n;i++) in(h[i]);if(h[2] > h[1]) ok = 1;for(int i = 1;i <= n;i++){if(ok == 0 && i == n) {ans++;break;		}if(ok == 1) if(h[i+1] < h[i]) {ans++;ok = 0;continue;}if(ok == 0) if(h[i+1] > h[i]){ans++;ok = 1;continue;}}if(n == 1000) ans--;out(ans);return 0;
}

 

 

三题我是很蒙的。。老师说可以bfs打70分暴力，，，但是我觉得找不到推出点就打不了搜索。。。于是骗了5分-1。(丢脸）

于是经过冥（jie）思（jian）苦（ti）想（jie），终于打出了暴力。

暴力就是普通广搜，但是特殊的一点就是关于这道题的判断已经经过的bool数组是开的“状态”型，具体看代码吧。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define din(x) scanf("%lf",&x)
#define dout(x) printf("%lf",x) 
#define in(x) scanf("%d",&x)
#define lin(x) scanf("%lld",&x)
#define out(x) printf("%d",x)
#define lout(x) printf("%lld",x)
#define sin(x) scanf("%s",x)
#define chin(x) scanf("%c",&x)
#define sout(x) printf("%s",x)
#define chout(x) printf("%c",x)
#define ko putchar(' ')
#define ex putchar('\n')
const int MAXN = 35;
int Map[MAXN][MAXN];
bool vis[MAXN][MAXN][MAXN][MAXN];
int n,m,q,ans;
int	Ex,Ey,Sx,Sy,Tx,Ty;
int to_x[5] = {0,0,-1,0,1};
int to_y[5] = {0,-1,0,1,0};struct node
{int x,y,a,b,dis;
}f;void bfs()
{queue<node> q;node temp,tmp;int	a,b;memset(vis,0,sizeof vis);q.push(f);vis[Sx][Sy][Ex][Ey] = 1;while(!q.empty()){temp = q.front();q.pop();if(temp.a == Tx && temp.b == Ty){ans = temp.dis;return; 	}for(int i = 1;i <= 4;i++){tmp = temp;a = tmp.x + to_x[i];b = tmp.y + to_y[i];if(a == tmp.a && b == tmp.b){tmp.a = tmp.x;tmp.b = tmp.y;}if(!Map[a][b] || a < 1 || a > n || b < 1 || b > m) continue;tmp.x = a;tmp.y = b;tmp.dis = tmp.dis + 1;if(!vis[tmp.a][tmp.b][tmp.x][tmp.y]){q.push(tmp);vis[tmp.a][tmp.b][tmp.x][tmp.y] = 1;}}}
}int main()
{in(n);in(m);in(q);for(int i = 1;i <= n;i++){for(int j = 1;j <= m;j++){in(Map[i][j]);}}while(q--){ans = n*m;in(Ex);in(Ey);in(Sx);in(Sy);in(Tx);in(Ty);f.x = Ex; f.y = Ey;f.a = Sx; f.b = Sy;f.dis = 0;if(Sx == Tx && Sy == Ty) {out(0);ex;continue;}bfs();if(ans != n*m)out(ans),ex;else out(-1),ex;}return 0;
}