记忆化搜索 get ！
简单：
传送门
一遍切黄！
话说省选题为什么这么简单
#define int long long
int cnt,n,m;
int head[4*MAXN],in[MAXN],out[MAXN];
int dp[MAXN];
int dfs(int u)
{
int ans = 0;
if(dp[u]) return dp[u];
if(in[u] && !out[u]) return dp[u] = 1;
for(int k=head[u];k;k=map[k].next)
{
int v = map[k].to;
dp[u] += dfs(v);
}
return dp[u];
}
signed main(void)
{
cin >> n >> m;
for(int i=1,u,v;i<=m;i++)
{
cin >> u >> v;
out[u]++;in[v]++;
add(u,v);
}
int ans = 0;
for(int i=1;i<=n;i++)
if(!in[i]) ans += dfs(i);
cout << ans;
}填坑：
传送门
这道题由于不好 DP ，所以采用记忆化搜索。
记录每个点向左右最远能到哪，
如果最后一行有未访问的点，输出 0
否则找最少建几个蓄水厂，
怎么找呢？
枚举一个左端点 L 如果某点最左能达到 L 的左边，
显然 L 左边的点也可以连通该点所能到的点，
所以用 R 记录该点的最右，更新 L 为 R+1 ，
即由于在之前的点最右也是小于 R+1 的，所以要新建一个厂
int maxL[MAXN][MAXN]; //最大能达到的左端点
int maxR[MAXN][MAXN]; //右端点
int vis[MAXN][MAXN];
int fx[4] = {0,0,-1,1};
int fy[4] = {1,-1,0,0};
void dfs(int x, int y)
{
vis[x][y] = 1;
for(int i=0;i<4;i++)
{
int nx = x+fx[i];
int ny = y+fy[i];
if(nx<1 || ny<1 || nx>n || ny>m)continue;
if(map[nx][ny] >= map[x][y]) continue;
if(!vis[nx][ny]) dfs(nx,ny);
maxL[x][y] = min(maxL[x][y],maxL[nx][ny]);
maxR[x][y] = max(maxR[x][y],maxR[nx][ny]);
}
}
int main(void)
{
memset(maxL,0x3f,sizeof maxL);
cin >> n >> m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin >> map[i][j];
for(int i=1;i<=m;i++)
maxL[n][i] = maxR[n][i] = i;
for(int i=1;i<=m;i++)
if(!vis[1][i]) dfs(1,i);
for(int i=1;i<=m;i++)
if(!vis[n][i])
{
ans++;
flag = 1;
}
if(flag)
{
cout << "0" << endl << ans;
return 0;
}
int R = 1,L = 1;
while(L <= m)
{
for(int i=L;i<=m;i++)
{
if(maxL[1][i] <= L)
R = max(R,maxR[1][i]);
else break;
}
L = R+1;
ans++;
}
cout << "1" << endl << ans;
return 0;
}