Luogu2919 [USACO08NOV]守护农场Guarding the Farm(DFS)

Luogu2919 [USACO08NOV]守护农场Guarding the Farm(DFS)

2019年11月5日 0 作者 Null NaN

Luogu2919 [USACO08NOV]守护农场Guarding the Farm(DFS)

代Sunset_Rl 发表,已获得本人许可

题目描述

The farm has many hills upon which Farmer John would like to place guards to ensure the safety of his valuable milk-cows.

He wonders how many guards he will need if he wishes to put one on top of each hill. He has a map supplied as a matrix of integers; the matrix has N (1 < N <= 700) rows and M (1 < M <= 700) columns. Each member of the matrix is an altitude H_ij (0 <= H_ij <= 10,000). Help him determine the number of hilltops on the map.

A hilltop is one or more adjacent matrix elements of the same value surrounded exclusively by either the edge of the map or elements with a lower (smaller) altitude. Two different elements are adjacent if the magnitude of difference in their X coordinates is no greater than 1 and the magnitude of differences in their Y coordinates is also no greater than 1.

输入格式

* Line 1: Two space-separated integers: N and M

* Lines 2..N+1: Line i+1 describes row i of the matrix with M

space-separated integers: H_ij

输出格式

* Line 1: A single integer that specifies the number of hilltops

题意翻译

农夫John的农场里有很多小山丘,他想要在那里布置一些保镖去保卫他的那些相当值钱的奶牛们。

他想知道如果在一座小山丘上布置一名保镖的话,他最少总共需要招聘多少名保镖。他现在手头有一个用数字矩阵来表示地形的地图。这个矩阵有N行(1<N≤700)和M列( 1<M≤ 700) 。矩阵中的每个元素都有一个值H_ij(0≤H_ij≤10000)来表示该地区的海拔高度。

小山丘的定义是:若地图中一个元素所邻接的所有元素都比这个元素高度要小(或它邻接的是地图的边界),则该元素和其周围所有按照这样顺序排列的元素的集合称为一个小山丘。这里邻接的意义是:若一个位置的横纵坐标与另一个位置的横纵坐标相差不超过1,则称这两个元素邻接,比如某个非边界点的位置有8个相邻点:上、下、左、右、左上、右上、左下、右下。

请你帮助他统计出地图上最少且尽量高的小山丘数量。

输入输出样例

输入 #1


8 7
4 3 2 2 1 0 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0

输出 #1


3

说明/提示

There are three peaks: The one with height 4 on the left top, one of the points with height 2 at the bottom part, and one of the points with height 1 on the right top corner.

先按照高度排序,然后从较高的点依次访问周边 <= 的点即可

“`c++
#include
#include
#include
#include
#include
using std::cin;
using std::cout;
void gkd()
{
std::ios::sync_with_stdio(false);
cout.tie(NULL);
}
const int maxn = 777;
int map[maxn][maxn], vis[maxn][maxn];
struct node
{
int x, y, h;
}pt[2333333];
bool cmp(node a, node b)
{
return a.h > b.h;
}
int move[8][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {-1, -1}, {1, -1}, {-1, 1}};
int n, m;
void dfs(int x, int y)
{
vis[x][y] = 1;
for(int i = 0; i < 8; i++)
{
int nowx = x + move[i][0];
int nowy = y + move[i][1];
if(nowx < 0 || nowy < 0 || nowx > n || nowy > m || vis[nowx][nowy])
continue;
if(map[nowx][nowy] <= map[x][y] && !vis[nowx][nowy])
dfs(nowx, nowy);
}
}
int main()
{
gkd();
cin >> n >> m;
int cnt = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
pt[++cnt].x = i;
pt[cnt].y = j;
cin >> map[i][j];
pt[cnt].h = map[i][j];
}
std::sort(pt + 1, pt + n * m + 1, cmp);
int ans = 0;
for(int i = 1; i <= n * m; i++)
if(!vis[pt[i].x][pt[i].y])
{
dfs(pt[i].x, pt[i].y);
ans++;
}
cout << ans;
}


————————————————————————————————————————

### Luogu 1825[USACO11OPEN]玉米田迷宫Corn Maze(BFS)

## 题目描述

This past fall, Farmer John took the cows to visit a corn maze. But this wasn't just any corn maze: it featured several gravity-powered teleporter slides, which cause cows to teleport instantly from one point in the maze to another. The slides work in both directions: a cow can slide from the slide's start to the end instantly, or from the end to the start. If a cow steps on a space that hosts either end of a slide, she must use the slide.

The outside of the corn maze is entirely corn except for a single exit.

The maze can be represented by an N x M (2 &lt;= N &lt;= 300; 2 &lt;= M &lt;= 300) grid. Each grid element contains one of these items:

\* Corn (corn grid elements are impassable)

\* Grass (easy to pass through!)

\* A slide endpoint (which will transport a cow to the other endpoint)

\* The exit

A cow can only move from one space to the next if they are adjacent and neither contains corn. Each grassy space has four potential neighbors to which a cow can travel. It takes 1 unit of time to move from a grassy space to an adjacent space; it takes 0 units of time to move from one slide endpoint to the other.

Corn-filled spaces are denoted with an octothorpe (#). Grassy spaces are denoted with a period (.). Pairs of slide endpoints are denoted with the same uppercase letter (A-Z), and no two different slides have endpoints denoted with the same letter. The exit is denoted with the equals sign (=).

Bessie got lost. She knows where she is on the grid, and marked her current grassy space with the 'at' symbol (@). What is the minimum time she needs to move to the exit space?

去年秋天,奶牛们去参观了一个玉米迷宫,迷宫里有一些传送装置,可以将奶牛从一点到另一点进行瞬间转移。这些装置可以双向使用:一头奶牛可以从这个装置的起点立即到此装置的终点,同时也可以从终点出发,到达这个装置的起点。如果一头奶牛处在这个装置的起点或者终点,这头奶牛就必须使用这个装置。

玉米迷宫的外部完全被玉米田包围,除了唯一的一个出口。

这个迷宫可以表示为N×M的矩阵(2 ≤ N ≤ 300; 2 ≤ M ≤ 300),矩阵中的每个元素都由以下项目中的一项组成:

 玉米,这些格子是不可以通过的。

 草地,可以简单的通过。

 一个装置的结点,可以将一头奶牛传送到相对应的另一个结点。

 出口

奶牛仅可以在相邻两个格子之间移动,要在这两个格子不是由玉米组成的前提下才可以移动。奶牛能在一格草地上可能存在的四个相邻的格子移动。从草地移动到相邻的一个格子需要花费一个单位的时间,从装置的一个结点到另一个结点需要花费0个单位时间。

被填充为玉米的格子用“#”表示,草地用“.”表示,每一对装置的结点由相同的大写字母组成“A-Z”,且没有两个不同装置的结点用同一个字母表示,出口用“=”表示。

Bessie在这个迷宫中迷路了,她知道她在矩阵中的位置,将Bessie所在的那一块草地用“@”表示。求出Bessie需要移动到出口处的最短时间。

例如以下矩阵,N=5,M=6:

###=##
#.W.##
#.####
#.@W##
######


唯一的一个装置的结点用大写字母W表示。

最优方案为:先向右走到装置的结点,花费一个单位时间,再到装置的另一个结点上,花费0个单位时间,然后再向右走一个,再向上走一个,到达出口处,总共花费了3个单位时间。

## 输入格式

第一行:两个用空格隔开的整数N和M;

第2-N+1行:第i+1行描述了迷宫中的第i行的情况(共有M个字符,每个字符中间没有空格。)

## 输出格式

一个整数,表示Bessie到达终点所需的最短时间。

## 输入输出样例

输入 #1

5 6
###=##
#.W.##
#.####
#.@W##
######


**输出 #1**

3


#### BFS,特殊处理传送器(注意有的传送器可能只有一台 ~~憨憨传送器~~)

```c++
#include&lt;iostream&gt;
#include&lt;cstdio&gt;
#include&lt;algorithm&gt;
#include&lt;cstring&gt;
#include&lt;cmath&gt;
#include&lt;queue&gt;
using std::cin;
using std::cout;
void gkd()
{
    std::ios::sync_with_stdio(false);
    cout.tie(NULL);
}

char map[333][333];//存迷宫
int step[333][333];//走的步数
int move[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
struct node
{
    int x, y;
}top, now, tp[30][2];//tp存的是传送机
std::queue&lt;node&gt; q;
int n, m, ans, ex, ey, sx, sy;
const int maxn = 1e9 + 7;

node find(char now, int a, int b)//找到另一台传送机的位置,方便传送
{
    node back;
    if(tp[now - 'A'][1].x != a || tp[now - 'A'][1].y != b)// 从2 - 1
    {
        back.x = tp[now - 'A'][1].x,
        back.y = tp[now - 'A'][1].y;
        return back;
    }
    else// 从1 -2
    {
        back.x = tp[now - 'A'][2].x,
        back.y = tp[now - 'A'][2].y;
        return back;
    }
}
bool check(char now)//是否存在另一台传送机(有的可能只有一台)
{
    return (tp[now - 'A'][2].x != 0);
}
void bfs(int x, int y)
{
    now.x = x;
    now.y = y;
    q.push(now);
    while( !q.empty())
    {
        top = q.front();
        q.pop();
        for(int i = 0; i &lt; 4; i++)
        {
            int nowx = top.x + move[i][0];
            int nowy = top.y + move[i][1];
            if(map[nowx][nowy] != '#')
            {
                if(map[nowx][nowy] &gt;= 'A' &amp;&amp; map[nowx][nowy] &lt;= 'Z' &amp;&amp; check(map[nowx][nowy]))//走传送机
                {
                    now = find(map[nowx][nowy], nowx, nowy);
                    if(step[now.x][now.y] &gt; step[top.x][top.y] + 1)
                    {
                        step[now.x][now.y] = step[top.x][top.y] + 1;
                        q.push(now);
                    }
                }
                else if(step[nowx][nowy] &gt; step[top.x][top.y] + 1)//不走传送机
                {
                    step[nowx][nowy] = step[top.x][top.y] + 1;
                    now.x = nowx;
                    now.y = nowy;
                    q.push(now);
                }
            }
        }
    }
}
int main()
{
    gkd();
    cin &gt;&gt; n &gt;&gt; m;
    for(int i = 1; i &lt;= n; i++)
        for(int j = 1; j &lt;= m; j++)
        {
            step[i][j] = maxn;
            cin &gt;&gt; map[i][j];
            if(map[i][j] == '@')
                sx = i, sy = j, step[i][j] = 0;
            else if(map[i][j] == '=')
                ex = i, ey = j;
            else if(map[i][j] &gt;= 'A' &amp;&amp; map[i][j] &lt;= 'Z')//处理传送机
            {
                int now = map[i][j];
                if(tp[now - 'A'][1].x != 0)//如果是第一台
                {
                    tp[now - 'A'][2].x = i;
                    tp[now - 'A'][2].y = j;
                }
                else//如果是第二台
                {
                    tp[now - 'A'][1].x = i;
                    tp[now - 'A'][1].y = j;
                }
            }
        }
    bfs(sx, sy);
    cout &lt;&lt; step[ex][ey];
}

&lt;/code&gt;&lt;/pre&gt;

————————————————————————————————————————

&lt;h3&gt;Luogu 2052[NOI2011]道路修建&lt;/h3&gt;

&lt;h2&gt;题目描述(DFS)&lt;/h2&gt;

在 W 星球上有 n 个国家。为了各自国家的经济发展,他们决定在各个国家 之间建设双向道路使得国家之间连通。但是每个国家的国王都很吝啬,他们只愿 意修建恰好 n – 1 条双向道路。 每条道路的修建都要付出一定的费用,这个费用等于道路长度乘以道路两端 的国家个数之差的绝对值。例如,在下图中,虚线所示道路两端分别有 2 个、4 个国家,如果该道路长度为 1,则费用为 1×|2 – 4|=2。图中圆圈里的数字表示国 家的编号。 &lt;img src="https://cdn.luogu.com.cn/upload/pic/2604.png" alt="img" /&gt;

由于国家的数量十分庞大,道路的建造方案有很多种,同时每种方案的修建 费用难以用人工计算,国王们决定找人设计一个软件,对于给定的建造方案,计 算出所需要的费用。请你帮助国王们设计一个这样的软件。

&lt;h2&gt;输入格式&lt;/h2&gt;

输入的第一行包含一个整数 n,表示 W 星球上的国家的数量,国家从 1 到 n 编号。 接下来 n – 1 行描述道路建设情况,其中第 i 行包含三个整数 ai、bi和 ci,表 示第 i 条双向道路修建在 ai与 bi两个国家之间,长度为 ci。

&lt;h2&gt;输出格式&lt;/h2&gt;

输出一个整数,表示修建所有道路所需要的总费用。

&lt;h2&gt;输入输出样例&lt;/h2&gt;

输入 #1

&lt;pre&gt;&lt;code class=""&gt;6
1 2 1
1 3 1
1 4 2
6 3 1
5 2 1
&lt;/code&gt;&lt;/pre&gt;

输出 #1

&lt;pre&gt;&lt;code class=""&gt;20
&lt;/code&gt;&lt;/pre&gt;

&lt;h2&gt;说明/提示&lt;/h2&gt;

1≤ai, bi≤n

0≤ci≤10^6

2≤n≤10^6

&lt;img src="https://cdn.luogu.com.cn/upload/pic/2603.png" alt="img" /&gt;

遍历树求解

一个非叶点的贡献为 |2 * size[x] - n| * e[x].val;

```c++
//简单计算,每个非叶节点的贡献为 |2 * size[x] - n| * e[i].val
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define int long long
using std::cin;
using std::cout;
void gkd()
{
    std::ios::sync_with_stdio(false);
    cout.tie(NULL);
}

const int maxn = 1e6 + 233;
struct node
{
    int from, to, val;
}e[maxn &lt;&lt; 1];
int n, cnt, ans, head[maxn], size[maxn];
void insert(int u, int v, int w)
{
    e[++cnt].from = head[u];
    e[cnt].to = v;
    e[cnt].val = w;
    head[u] = cnt;
}
void dfs(int x, int fa)
{
    size[x] = 1;
    for(int i = head[x]; i; i = e[i].from)
    {
        if(e[i].to != fa)
        {
            dfs(e[i].to, x);
            ans += abs(n - 2 * size[e[i].to]) * e[x].val;
            size[x] += size[e[i].to];
        }
    }
}
signed main()
{
    gkd();
    cin &gt;&gt; n;
    for(int i = 1; i &lt;= n - 1; i++)
    {
        int x, y, z;
        cin &gt;&gt; x &gt;&gt; y &gt;&gt; z;
        insert(x, y, z);
        insert(y, x, z);
    }
    dfs(1, 1);
    cout &lt;&lt; ans;
}





<pre><code class="">
————————————————————————————————————————

### Luogu2208 [USACO13OPEN]重力异常What's Up With Gra…

## 题目描述

Captain Bovidian is on an adventure to rescue her crew member, Doctor Beefalo. Like all great adventures, this story plays out in a two dimensional N by M grid (1 &lt;= N, M &lt;= 500), representing a side view of the captain's world. Some grid cells are empty while others are blocked and cannot be traversed.

Unfortunately, Captain Bovidian cannot jump. She must obey the following rules of physics while traversing her world.

1. If there is no cell directly underneath Captain Bovidian (that is, if she is at the edge of the grid), then she flies out into space and fails her mission.
2. If the cell directly underneath Captain Bovidian is empty, then she falls into that cell.
3. Otherwise:

a) Captain Bovidian may move left or right if the corresponding cell exists and is empty.

b) Or, Captain Bovidian may flip the direction of gravity.

When Captain Bovidian changes the direction of gravity, the cell that's 'underneath' her (as mentioned in rules 1 and 2) toggles between the cell with one higher row index and the cell with one lower row index (the first row in the input has index 1, and the last row has index N). Initially, the cells with one higher row index are underneath Captain Bovidian.

Doctor Beefalo is lost somewhere in this world. Help Captain Bovidian arrive at her cell using the least number of gravity flips as possible. If it is impossible to reach Doctor Beefalo, please output -1.

Bovidian 船长正在拯救她的船员,Beefalo 博士。

和所有伟大的冒险故事一样,这个故事也是发生在一个2D平面上的。囧

这个平面是M*N的格子组成的网格,代表着船长的世界的一个侧视图。

有些格子是空的,另一些则是实心的,并且不能直接通过。

很不幸的是,船长跳不起来。她必须遵守这个世界的特殊物理法则。

1)如果船长的正下方没有方块(换句话说,即使她正在网格的边缘),那么她就会掉入宇宙中,同时意味着冒险失败。

2)如果船长的正下方的方块是空的,那么她就会掉到这个方块,

3)在不满足1)与2)的情况下,船长可以做一下的事情:

a) 如果左边(或右边)的方格是空的,那么她可以走到那个格子。

b船长可以翻转重力的方向

当船长改变翻转重力的方向时,我们就改变船长”下方“的定义。

”下方“的定义只能是两种

(A)比船长位置所在的方格的列编号更大的格子,

(B)比船长位置所在的方格的列编号更小的格子,

一开始的时候,“下方”的定义是比船长位置所在方格的列编号更大的格子。

Beefalo博士正迷失在这个世界中的某一处,请帮助船长从起点到达博士的地方。

如果可以到达,请输出最少需要的翻转重力的次数。

如果不可以到达,请输出-1

## 输入格式

第1行输入两个整数 N,M

第2行到N+1行中,第i+1行则是代表船长世界的第i行。每行有M个字符。

其中","代表着一个空的格子,"#"代表着一个实心的格子,"C"代表着船长的位置,"D"代表着博士的位置。

## 输出格式

一行,输出一个整数。

如果船长可以到达,请输出最少需要的翻转重力的次数。

如果不可以到达,请输出-1

## 输入输出样例

输入 #1

5 5
#####
#…#
#…D
#C…
##.##


输出 #1

3


## 说明/提示

输出解释:

首先,船长在(4,2),接着她翻转重力,到达(2,2)

接着她向右走走到(2,4),接着她第二次翻转重力,到达(4,4)

然后她继续向右走到(4,5),最后在翻转一次重力,到达博士所在的(3,5)

### 重点处理重力的相关状态

```c++
#include&lt;map&gt;
#include&lt;stack&gt;
#include&lt;cmath&gt;
#include&lt;queue&gt;
#include&lt;cstdio&gt;
#include&lt;vector&gt;
#include&lt;cstring&gt;
#include&lt;iostream&gt;
#include&lt;algorithm&gt;
using std::cin;
using std::cout;
void gkd()
{
    std::ios::sync_with_stdio(false);
    cout.tie(NULL);
}
char map[555][555];
bool vis[555][555][4];
struct node
{
    int x, y, g, sum;//当前坐标,当前重力状态:1为上 -1为下
}now, top;
std::deque&lt;node&gt; q;
int n, m, x, y;
signed main()
{
    //gkd();
    cin &gt;&gt; n &gt;&gt; m;
    for(int i = 1; i &lt;= n; i++)
    {
        scanf("%s",map[i]+1);
        for(int j = 1; j &lt;= m; j++)
        {
            if(map[i][j] == 'C')
                x = i, y = j;
        }
    }
    now.x = x, now.y = y, now.g = 1, now.sum = 0;
    q.push_back(now);
    while(!q.empty())
    {
        top = q.front();
        q.pop_front();
        now.x = top.x + top.g,
        now.y = top.y,
        now.g = top.g,
        now.sum = top.sum;
        if(map[top.x][top.y] == 'D')
            return cout &lt;&lt; top.sum, 0;
        if(top.x + top.g &lt; 1 || top.x + top.g &gt; n || top.y &lt; 1 || top.y &gt; m)
            continue;//越了上下边界
        vis[top.x][top.y][top.g + 1] = 1;
        if(map[top.x  + top.g][top.y] == '#')//脚下(头上)能不能踩
        {
            now.x = top.x,
            now.y = top.y + 1,
            now.g = top.g,
            now.sum = top.sum;
            if(!vis[top.x][top.y + 1][top.g + 1] &amp;&amp; map[top.x][top.y + 1] != '#')
                q.push_front(now);//判断当前的重力下右移

            now.x = top.x,
            now.y = top.y - 1,
            now.g = top.g,
            now.sum = top.sum;
            if(!vis[top.x][top.y - 1][top.g + 1] &amp;&amp; map[top.x][top.y - 1] != '#')
                q.push_front(now);//判断当前重力下左移

            now.x = top.x,
            now.y = top.y,
            now.g =- top.g,
            now.sum = top.sum + 1;
            if(!vis[top.x][top.y][-top.g + 1])
                q.push_back(now);//翻转重力        
        }
        else
            q.push_front(now);//如果脚下不是可以踩的格子,那么就继续下落或者上落    
    }
    cout &lt;&lt; -1 &lt;&lt; '\n';
}
&lt;/code&gt;&lt;/pre&gt;

————————————————————————————————————————

&lt;h3&gt;Luogu 2279 [HNOI2003]消防局的设立&lt;/h3&gt;

&lt;h2&gt;题目描述&lt;/h2&gt;

2020年,人类在火星上建立了一个庞大的基地群,总共有n个基地。起初为了节约材料,人类只修建了n-1条道路来连接这些基地,并且每两个基地都能够通过道路到达,所以所有的基地形成了一个巨大的树状结构。如果基地A到基地B至少要经过d条道路的话,我们称基地A到基地B的距离为d。

由于火星上非常干燥,经常引发火灾,人类决定在火星上修建若干个消防局。消防局只能修建在基地里,每个消防局有能力扑灭与它距离不超过2的基地的火灾。

你的任务是计算至少要修建多少个消防局才能够确保火星上所有的基地在发生火灾时,消防队有能力及时扑灭火灾。

&lt;h2&gt;输入格式&lt;/h2&gt;

输入文件名为input.txt。

输入文件的第一行为n (n&lt;=1000),表示火星上基地的数目。接下来的n-1行每行有一个正整数,其中文件第i行的正整数为a[i],表示从编号为i的基地到编号为a[i]的基地之间有一条道路,为了更加简洁的描述树状结构的基地群,有a[i]&lt;i。

&lt;h2&gt;输出格式&lt;/h2&gt;

输出文件名为output.txt

输出文件仅有一个正整数,表示至少要设立多少个消防局才有能力及时扑灭任何基地发生的火灾。

&lt;h2&gt;输入输出样例&lt;/h2&gt;

输入 #1

&lt;pre&gt;&lt;code class=""&gt;6
1
2
3
4
5
&lt;/code&gt;&lt;/pre&gt;

输出 #1

&lt;pre&gt;&lt;code class=""&gt;2
&lt;/code&gt;&lt;/pre&gt;

​   &lt;a href="https://www.luogu.org/blog/rickole/solution-p2279"&gt;树形dp讲解&lt;/a&gt;

​   树形dp &amp;&amp; 贪心(本人觉得贪心好理解,树形dp也不难)

```c++
/*
F[i][0]表示可以覆盖到从节点i向上2层的最小消防站个数
F[i][1]表示可以覆盖到从节点i向上1层的最小消防站个数
F[i][2]表示可以覆盖到从节点i向上0层的最小消防站个数
F[i][3]表示可以覆盖到从节点i向上-1层的最小消防站个数
F[i][4]表示可以覆盖到从节点i向上-2层的最小消防站个数
*/
#include<map>
#include<stack>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using std::cin;
using std::cout;
void gkd()
{
    std::ios::sync_with_stdio(false);
    cout.tie(NULL);
}
const int inf = 1e9 + 7;
const int maxn = 1111;
int cnt, head[maxn];
struct node
{
    int from, to;
}e[maxn &lt;&lt; 1];
void insert(int u, int v)
{
    e[++cnt].from = head[u];
    e[cnt].to = v;
    head[u] = cnt;
}

int f[maxn][5];
void dfs(int x)
{
    f[x][0] = 1;//自己是消防局
    f[x][3] = 0;//儿子被覆盖
    f[x][4] = 0;//孙子被覆盖
    for(int i = head[x]; i; i  = e[i].from)
    {
        int to = e[i].to;
        dfs(to);
        f[x][0] += f[to][4];//自己是消防局时,儿子所需要最小的消防局即是父亲的加上自己儿子以下的(儿子的儿子已经被自己覆盖)
        f[x][3] += f[to][2];
        //所有儿子覆盖,则儿子不需要再覆盖
        f[x][4] += f[to][3];
        //孙子全被覆盖,即儿子的儿子全被覆盖
    }
    if(head[x] == 0)
    {
        f[x][1] = f[x][2] = 1;//根节点的向上一层和两层
    }
    else
    {
        f[x][1] = f[x][2] = inf;//初始化非根节点的消防局个数
        for(int i = head[x]; i; i = e[i].from)
        {
            int to = e[i].to;
            int f1 = f[to][0];//儿子覆盖父亲及爷爷
            int f2 = f[to][1];//孙子覆盖爷爷
            for(int j = head[x]; j; j = e[j].from)
            {
                if(i == j)
                    continue;
                int too = e[j].to;
                f1 += f[too][3];//既然一个儿子已经是消防局,其他儿子只需要覆盖他们的儿子即可
                f2 += f[too][2];//其他的儿子就得从自己开始覆盖
            }
            f[x][1] = std::min(f[x][1], f1);//统计更新答案
            f[x][2] = std::min(f[x][2], f2);
        }
    }
    for(int i = 1; i &lt;= 4; i++)
        f[x][i] = std::min(f[x][i], f[x][i - 1]);//四种情况取最小值
}
int main()
{
    gkd();
    int n;
    cin &gt;&gt; n;
    for(int i = 2; i &lt;= n; i++)
    {
        int a;
        cin &gt;&gt; a;
        insert(a, i);
    }
    dfs(1);
    cout &lt;&lt; f[1][2];//根节点及他之上的不需要被覆盖,所以仅需要f[1][2]即可
}

/*









<hr>









对于深度最大的叶子节点,就需要一个消防局去覆盖他
覆盖他的节点:1 父亲 2兄弟 3 爷爷
由此可得,兄弟和父亲能覆盖的点,爷爷可以全部覆盖
每次找深度最大的点,在他爷爷放消防局

int dep[maxn], fa[maxn];
bool vis[maxn];
struct cmp
{
    bool operator()(int &amp;a, int &amp;b)
    {
        return dep[a] &lt; dep[b];
    }
};
std::priority_queue&lt;int, std::vector<int>, cmp&gt; q;
void dfs_fir(int x, int father, int depth)
{
    fa[x] = father;
    dep[x] = depth;
    for(int i = head[x]; i; i = e[i].from)
    {
        if(e[i].to == father)
            continue;
        dfs_fir(e[i].to, x, depth + 1);
    }
}//求深度

void dfs_sec(int x, int depth)
{
    if(depth &gt; 2)
        return;
    vis[x] = true;
    for(int i = head[x]; i; i = e[i].from)
        dfs_sec(e[i].to, depth + 1);
}//把他到他爷爷路径全标上

int main()
{
    gkd();
    int n, cntt, x, y, ans = 0;
    cin &gt;&gt; n;
    cntt = n;
    for(int i = 1; i &lt;= n - 1; i++)
    {
        cin &gt;&gt; x;
        insert(i + 1, x);
        insert(x, i + 1);
    }
    dfs_fir(1, 0, 1);
    for(int i = 1; i &lt;= n; i++)
        q.push(i);
     while( q.size() )//利用优先队列的特性,从叶结点开始
     {
        while(q.size() &amp;&amp; vis[x = q.top()])
            q.pop();
        if( !q.size())
            break;
        if(fa[fa[x]])
            dfs_sec(fa[fa[x]], 0);
        else
            dfs_sec(1,0);
        ans++; //计数
    }
    cout &lt;&lt; ans;
}
*/





<pre><code class="">
————————————————————————————————————————

### Luogu 3659 [USACO17FEB]Why Did the Cow Cross the Road I G

## 题目描述

Why did the cow cross the road? Well, one reason is that Farmer John's farm simply has a lot of roads, making it impossible for his cows to travel around without crossing many of them.

奶牛们为什么要穿马路?一个原因只是因为FJ的牧场的路实在是太多了,使得奶牛们每天不得不穿梭在许许多多的马路中央

FJ's farm is arranged as an N \times N*N*×*N* square grid of fields (3 \leq N \leq 1003≤*N*≤100), with a set of N-1*N*−1north-south roads and N-1*N*−1 east-west roads running through the interior of the farm serving as dividers between the fields. A tall fence runs around the external perimeter, preventing cows from leaving the farm. Bessie the cow can move freely from any field to any other adjacent field (north, east, south, or west), as long as she carefully looks both ways before crossing the road separating the two fields. It takes her T*T* units of time to cross a road (0 \leq T \leq 1,000,0000≤*T*≤1,000,000).

FJ的牧场可以看作是一块 N\times N*N*×*N* 的田地(3\le N\le 1003≤*N*≤100),N-1*N*−1 条南北向的道路和 N-1*N*−1 条东西向的道路贯穿整个牧场,同时是每块田野的分界线。牧场的最外面是一圈高大的栅栏以防止奶牛离开牧场。Bessie只要穿过分离两块田野的道路,就可以从任何田野移动到与其相邻的田野里去(北,东,南或西)。当然,Bessie穿过每一条马路都是需要T*T* 时间的。(0\le T\le 1,000,0000≤*T*≤1,000,000)

One day, FJ invites Bessie to visit his house for a friendly game of chess. Bessie starts out in the north-west corner field and FJ's house is in the south-east corner field, so Bessie has quite a walk ahead of her. Since she gets hungry along the way, she stops at every third field she visits to eat grass (not including her starting field, but including possibly the final field in which FJ's house resides). Some fields are grassier than others, so the amount of time required for stopping to eat depends on the field in which she stops.

有一天,FJ邀请Bessie来他家下棋,Bessie从牧场的西北角出发,FJ的家在牧场的东南角。因为Bessie在中途可能会饿,所以她每走过三块田野就要停下来,享用她所在田野上的新鲜的牧草(不包括Bessie的出发点,但是可能会包括终点FJ的家),牧场上有些田野的牧草长得比其他地方茂盛,所以Bessie对应的停留时间也会变长。

Please help Bessie determine the minimum amount of time it will take to reach FJ's house.

请帮帮Bessie计算出她走到FJ家的最短时间。

## 输入格式

The first line of input contains N*N* and T*T*. The next N*N* lines each contain N*N* positive integers (each at most 100,000) describing the amount of time required to eat grass in each field. The first number of the first line is the north-west corner.

接下来 N*N* 行,每行 N*N* 个数表示每块田野Bessie需要停留的时间(每块最多不超过100,000100,000),第一行的第一块田野是牧场的西北角

## 输出格式

Print the minimum amount of time required for Bessie to travel to FJ's house.

一行一个整数表示Bessie走到FJ家的最短时间

## 输入输出样例

输入 #1

4 2
30 92 36 10
38 85 60 16
41 13 5 68
20 97 13 80


输出 #1

31


## 说明/提示

The optimal solution for this example involves moving east 3 squares (eating the "10"), then moving south twice and west once (eating the "5"), and finally moving south and east to the goal.

对于样例,Bessie先向东走过了三块田野(在“10”停留),再向南走两步,又向西走了一步(在“5”停留),最后向南走一步,再向东走一步到达FJ的家(不用停留),总共时间是15(停留时间)+16(穿马路时间)=31

感谢@jzqjzq 提供翻译



#### BFS + DP

#include

#include
#include
#include
#include
#include
#include
#include
#include
using std::cin;
using std::cout;
void gkd()
{
std::ios::sync_with_stdio(false);
cout.tie(NULL);
}
struct node
{
int x, y;
}now, top;
std::queue q;
int n, t, map[111][111], f[111][111][4];
int move[4][2] = {{0, 1}, {1,0}, {-1, 0}, {0, -1}};
int bfs()//bfs套dp,扩展时对于每个点分三种情况讨论取最小步数(步数为1, 步数为2,步数为3(
{
memset(f, 0x3f, sizeof(f));
f[1][1][0] = 0;
now.x = 1, now.y = 1;
q.push(now);
while(!q.empty())
{
top = q.front();
q.pop();
for(int i = 0; i < 4; i++)
{
int nowx = top.x + move[i][0], nowy = top.y + move[i][1];
bool flag = false;
if(nowx <= n && nowx > 0 && nowy <= n && nowy > 0)
{
if(f[top.x][top.y][0] + t < f[nowx][nowy][1])
{
f[nowx][nowy][1] = f[top.x][top.y][0] + t;
flag = true;
}
if(f[top.x][top.y][1] + t < f[nowx][nowy][2])
{
f[nowx][nowy][2] = f[top.x][top.y][1] + t;
flag = true;
}
if(f[top.x][top.y][2] + t + map[nowx][nowy] < f[nowx][nowy][0])
{
f[nowx][nowy][0] = f[top.x][top.y][2] + t + map[nowx][nowy];
flag = true;
}
if(flag)
{
now.x = nowx, now.y = nowy;
q.push(now);
}
}
}
}
return std::min(std::min(std::min(f[n][n][3], f[n][n][0]), f[n][n][1]), f[n][n][2]);
}
int main()
{
gkd();
cin >> n >> t;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
cin >> map[i][j];
cout << bfs();
return 0;
}


————————————————————————————————————————

### Luogu 2845 [USACO15DEC]Switching on the Lights 开关灯

## 题目背景

来源:usaco-2015-dec

Farm John 最近新建了一批巨大的牛棚。这些牛棚构成了一个N*N的矩形网络。(1&lt;n&lt;100)

然而bessie十分怕黑,他想计算可以把多少个牛棚的灯打开。

## 题目描述

有N*N个房间,组成了一张N*N的网格图,Bessie一开始位于左上角(1,1),并且只能上下左右行走。

一开始,只有(1,1)这个房间的灯是亮着的,Bessie只能在亮着灯的房间里活动。

有另外M条信息,每条信息包含四个数a,b,c,d,表示房间(a,b)里有房间(c,d)的灯的开关。

请计算出最多有多少个房间的灯可以被打开

## 输入格式

第一行,两个数:N,M(1&lt;m&lt;200000);

第2-m+1行:坐标(x1,y1),(x2,y2)代表房间的坐标(x1,y1)及可以点亮的·房间的坐标(x2,y2);

## 输出格式

一个数,最多可以点亮的房间数

## 输入输出样例

输入 #1

3 6
1 1 1 2
2 1 2 2
1 1 1 3
2 3 3 1
1 3 1 2
1 3 2 1


输出 #1

5


## 说明/提示

这里,如果你看得懂英文的话,这里有样例的说明。

Here, Bessie can use the switch in (1,1)to turn on lights in (1,2)and (1,3). She can then walk to (1,3)and turn on the lights in (2,1),from which she can turn on the lights in (2,2). The switch in (2,3)is inaccessible to her, being in an unlit room. She can therefore illuminate at most 5 rooms.

#### BFS扩展的时候记得看看新开灯的房间有没有可以访问的

```c++
#include&lt;map&gt;
#include&lt;stack&gt;
#include&lt;cmath&gt;
#include&lt;queue&gt;
#include&lt;cstdio&gt;
#include&lt;vector&gt;
#include&lt;cstring&gt;
#include&lt;iostream&gt;
#include&lt;algorithm&gt;
using std::cin;
using std::cout;
void gkd()
{
    std::ios::sync_with_stdio(false);
    cout.tie(NULL);
}
int move[4][2] = { {0, 1}, {1, 0}, {-1, 0}, {0, -1}};
struct node
{
    int x, y;
}top, now, temp;
const int maxn = 111;
std::vector&lt;node&gt; lamp[maxn][maxn];//每个房间控制的相关房间
bool map[maxn][maxn], vis[maxn][maxn];//map开没开灯,有没有访问房间
int n, m, ans;
void bfs()
{
    std::queue&lt;node&gt; q;
    now.x = 1, now.y = 1;
    q.push(now);
    vis[1][1] = true;
    map[1][1] = true;
    ans++;
    while(!q.empty())
    {
        top = q.front();
        q.pop();
        for(int i = 0; i &lt; 4; i++)
        {
            int nowx = top.x + move[i][0];
            int nowy = top.y + move[i][1];
            if(nowx &lt; 1 || nowx &gt; n || nowy &lt; 1 || nowy &gt; n || vis[nowx][nowy])
                continue;
            if(map[nowx][nowy])//灯开着且相邻就访问
                q.push((node){nowx, nowy}), vis[nowx][nowy] = 1;
        }
        for(int i = 0; i &lt; lamp[top.x][top.y].size(); i++)//看看当前房间控制的房间有没有与以前访问的相连的
        {                                               //以前访问不了现在可以访问的
            temp = lamp[top.x][top.y][i];
            if(vis[temp.x][temp.y] || map[temp.x][temp.y])
                continue;
            map[temp.x][temp.y] = 1;
            ans++;
            for(int i = 0; i &lt; 4; i++)
                if(vis[temp.x + move[i][0]][temp.y + move[i][1]])
                {
                    q.push((node){temp.x, temp.y}), vis[temp.x][temp.y] = 1;
                    break;
                }
        }
    }
}
int main()
{
    gkd();
    cin &gt;&gt; n &gt;&gt; m;
    for(int i = 1; i &lt;= m; i++)
    {
        int x1, y1, x2, y2;
        cin &gt;&gt; x1 &gt;&gt; y1 &gt;&gt; x2 &gt;&gt; y2;
        lamp[x1][y1].push_back((node){x2, y2});
    }
    bfs();
    cout &lt;&lt; ans;
    return 0;
}

&lt;/code&gt;&lt;/pre&gt;

————————————————————————————————————————

&lt;h3&gt;Luogu 3070 [USACO13JAN]岛游记Island Travels&lt;/h3&gt;

&lt;h2&gt;题目描述&lt;/h2&gt;

Farmer John has taken the cows to a vacation out on the ocean! The cows are living on N (1 &lt;= N &lt;= 15) islands, which are located on an R x C grid (1 &lt;= R, C &lt;= 50). An island is a maximal connected group of squares on the grid that are marked as 'X', where two 'X's are connected if they share a side. (Thus, two 'X's sharing a corner are not necessarily connected.)

Bessie, however, is arriving late, so she is coming in with FJ by helicopter. Thus, she can first land on any of the islands she chooses. She wants to visit all the cows at least once, so she will travel between islands until she has visited all N of the islands at least once.

FJ's helicopter doesn't have much fuel left, so he doesn't want to use it until the cows decide to go home. Fortunately, some of the squares in the grid are shallow water, which is denoted by 'S'. Bessie can swim through these squares in the four cardinal directions (north, east, south, west) in order to travel between the islands. She can also travel (in the four cardinal directions) between an island and shallow water, and vice versa.

Find the minimum distance Bessie will have to swim in order to visit all of the islands. (The distance Bessie will have to swim is the number of distinct times she is on a square marked 'S'.) After looking at a map of the area, Bessie knows this will be possible.

给你一张r*c的地图,有’S’,’X’,’.’三种地形,所有判定相邻与行走都是四连通的。我们设’X’为陆地,一个’X’连通块为一个岛屿,’S’为浅水,’.’为深水。刚开始你可以降落在任一一块陆地上,在陆地上可以行走,在浅水里可以游泳。并且陆地和浅水之间可以相互通行。但无论如何都不能走到深水。你现在要求通过行走和游泳使得你把所有的岛屿都经过一边。Q:你最少要经过几个浅水区?保证有解。

&lt;h2&gt;输入格式&lt;/h2&gt;

* Line 1: Two space-separated integers: R and C.

* Lines 2..R+1: Line i+1 contains C characters giving row i of the grid. Deep water squares are marked as '.', island squares are marked as 'X', and shallow water squares are marked as 'S'.

&lt;h2&gt;输出格式&lt;/h2&gt;

* Line 1: A single integer representing the minimum distance Bessie has to swim to visit all islands.

&lt;h2&gt;输入输出样例&lt;/h2&gt;

输入 #1

&lt;pre&gt;&lt;code class=""&gt;5 4
XX.S
.S..
SXSS
S.SX
..SX
&lt;/code&gt;&lt;/pre&gt;

输出 #1

&lt;pre&gt;&lt;code class=""&gt;3
&lt;/code&gt;&lt;/pre&gt;

&lt;h2&gt;说明/提示&lt;/h2&gt;

There are three islands with shallow water paths connecting some of them.

Bessie can travel from the island in the top left to the one in the middle, swimming 1 unit, and then travel from the middle island to the one in the bottom right, swimming 2 units, for a total of 3 units.

BFS找连通块 + 最短路 + 状压DP

```c++
#include<map>
#include<stack>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using std::cin;
using std::cout;
const int maxn = 55;
char map[maxn][maxn];//地图
bool vis[maxn][maxn];//是否访问过
struct node
{
    int x, y;
}tm[16][16];//记录连通块中每个成员的位置
//        当前属于哪个连通块,当前连通块大小
int n, m, unicom[maxn][maxn], size[maxn], dis[maxn][maxn];
int f[maxn][maxn], ans = 1 &lt;&lt; 30, dp[1 &lt;&lt; 16][16];
int move[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int cnt;
std::queue<node> q;
void bfs(int x, int y)//求出所有连通块
{
    node now;
    now.x = x;
    now.y = y;
    q.push(now);
    vis[x][y] = 1;
    unicom[x][y] = cnt;//所属连通块
    size[cnt]++;//连通块大小
    tm[cnt][size[cnt]].x = x;
    tm[cnt][size[cnt]].y = y;
    while(!q.empty())
    {
        node top;
        top = q.front();
        q.pop();
        for(int i = 0; i &lt; 4; i++)
        {
            int nowx = top.x + move[i][0];
            int nowy = top.y + move[i][1];
            if(nowx &gt;= 1 &amp;&amp; nowx &lt;= n &amp;&amp; nowy &gt;= 1 &amp;&amp; nowy &lt;= m &amp;&amp; !vis[nowx][nowy] &amp;&amp; map[nowx][nowy] == 'X')
            {
                node tmp;
                tmp.x = nowx;
                tmp.y = nowy;
                q.push(tmp);
                unicom[nowx][nowy] = cnt;
                size[cnt]++;
                vis[nowx][nowy] = 1;
                tm[cnt][size[cnt]].x = nowx;
                tm[cnt][size[cnt]].y = nowy;
            }
        }
    }
}
void spfa(int w)//求出各个连通块之间的最短距离
{
    memset(vis, 0, sizeof(vis));
    memset(dis, 127/3, sizeof(dis));
    for(int i = 1; i &lt;= size[w]; i++)
    {
        int nowx = tm[w][i].x;
        int nowy = tm[w][i].y;
        vis[nowx][nowy] = 1;
        dis[nowx][nowy] = 0;
        q.push(tm[w][i]);
    }//连通块内部的点相互到达距离为1
    while(!q.empty())
    {
        node top;
        top = q.front();
        q.pop();
        vis[top.x][top.y] = 0;
        for(int i = 0; i &lt; 4; i++)
        {
            int nowx = top.x + move[i][0];
            int nowy = top.y + move[i][1];
            if(nowx &lt;= 0 || nowx &gt; n || nowy &lt;= 0 || nowy &gt; m || map[nowx][nowy] == '.')
                continue;
            if(map[nowx][nowy] == 'X')//如果是一直在陆地上走,因为相互间距离为0,可以相互更新最短路
            {
                if(dis[nowx][nowy] &gt; dis[top.x][top.y])
                {
                    dis[nowx][nowy] = dis[top.x][top.y];
                    if(!vis[nowx][nowy])
                    {
                        vis[nowx][nowy] = 1;
                        q.push((node){nowx, nowy});
                    }
                }
                f[unicom[nowx][nowy]][w] = f[w][unicom[nowx][nowy]] = std::min
                (f[unicom[nowx][nowy]][w], dis[nowx][nowy]);//连通块间的最短距离
            }
            else
            {
                if(dis[top.x][top.y] + 1 &lt; dis[nowx][nowy])//走浅水区
                {
                    dis[nowx][nowy] = dis[top.x][top.y] + 1;
                    if(!vis[nowx][nowy])
                    {
                        vis[nowx][nowy] = 1;
                        q.push((node){nowx, nowy});
                    }
                }
            }
        }
    }
}
void DP()//状压
{
    memset(dp, 127/3, sizeof(dp));
    int temp = (1 &lt;&lt; cnt) - 1;//经过岛的状态
    for(int i = 1; i &lt;= cnt; i++)
        dp[1 &lt;&lt;(i - 1)][i] = 0;//自己到自己距离为0
    for(int s = 1; s &lt;= temp; s++)//每一个状态
    {
        for(int i = 1; i &lt;= cnt; i++)//走哪个岛
            if(s &amp; (1 &lt;&lt; (i - 1)))//走这个岛
            {
                for(int j = 1; j &lt;= cnt; j++)
                {
                    if(i == j)//走的不是他自己
                        continue;
                    dp[s][i] = std::min(dp[s][i], dp[s ^ (1 &lt;&lt; (i - 1))][j] + f[j][i]);
                                                //到这个岛的距离是本身还是由其他的转移
                }
            }
    }
}
int main()
{
    cin &gt;&gt; n &gt;&gt; m;
    for(int i = 1; i &lt;= n; i++)
    {
        scanf ("%s",map[i]+1);
    }
    for(int i = 1; i &lt;= n; i++)
        for(int j = 1; j &lt;= m; j++)
        {
            if(!vis[i][j] &amp;&amp; map[i][j] == 'X')//跑出连通块
            {
                cnt++;
                bfs(i, j);
            }
        }
    memset(f, 127/3, sizeof(f));
    for(int i = 1; i &lt;= cnt; i++)
        f[i][i] = 0, spfa(i);//跑出连通块间的最短距离
    DP();
    int s = (1 &lt;&lt; cnt) - 1;
    for(int i = 1; i &lt;= cnt; i++)//从哪个岛开始走
        ans = std::min(ans, dp[s][i]);//状压
    cout &lt;&lt; ans;
    return 0;

}


</node></algorithm></iostream></cstring></vector></cstdio></queue></cmath></stack></map>

<code class="">
————————————————————————————————————————————————————————————————————————————

### Luogu2744 [USACO5.3]量取牛奶Milk Measuring

## 题目描述

农夫约翰要量取 Q(1 &lt;= Q &lt;= 20,000)夸脱(夸脱,quarts,容积单位——译者注) 他的最好的牛奶,并把它装入一个大瓶子中卖出。消费者要多少,他就给多少,从不有任何误差。

农夫约翰总是很节约。他现在在奶牛五金商店购买一些桶,用来从他的巨大的牛奶池中量出 Q 夸脱的牛奶。每个桶的价格一样。你的任务是计算出一个农夫约翰可以购买的最少的桶的集合,使得能够刚好用这些桶量出 Q 夸脱的牛奶。另外,由于农夫约翰必须把这些桶搬回家,对于给出的两个极小桶集合,他会选择“更小的”一个,即:把这两个集合按升序排序,比较第一个桶,选择第一个桶容积较小的一个。如果第一个桶相同,比较第二个桶,也按上面的方法选择。否则继续这样的工作,直到相比较的两个桶不一致为止。例如,集合 {3,5,7,100} 比集合 {3,6,7,8} 要好。

为了量出牛奶,农夫约翰可以从牛奶池把桶装满,然后倒进瓶子。他决不把瓶子里的牛奶倒出来或者把桶里的牛奶倒到别处。用一个容积为 1 夸脱的桶,农夫约翰可以只用这个桶量出所有可能的夸脱数。其它的桶的组合没有这么方便。

计算需要购买的最佳桶集,保证所有的测试数据都至少有一个解。

## 输入格式

Line 1: 一个整数 Q

Line 2: 一个整数P(1 &lt;= P &lt;= 100),表示商店里桶的数量

Lines 3..P+2: 每行包括一个桶的容积(1 &lt;= 桶的容积 &lt;= 10000)

## 输出格式

输出文件只有一行,由空格分开的整数组成:

为了量出想要的夸脱数,需要购买的最少的桶的数量,接着是:

一个排好序的列表(从小到大),表示需要购买的每个桶的容积

## 输入输出样例

**输入 #1**复制

**输出 #1**复制

## 说明/提示

题目翻译来自NOCOW。

USACO Training Section 5.3

```c++
#include&lt;map&gt;
#include&lt;stack&gt;
#include&lt;cmath&gt;
#include&lt;queue&gt;
#include&lt;cstdio&gt;
#include&lt;vector&gt;
#include&lt;cstring&gt;
#include&lt;iostream&gt;
#include&lt;algorithm&gt;
using std::cin;
using std::cout;
void gkd()
{
    std::ios::sync_with_stdio(false);
    cout.tie(NULL);
}
int n, m;
int bo[111];//桶的容量
int temp[111], ans[111], flag;//临时答案,最终答案
bool find = false;
void dfs(int k, int v, int s)//当前结果数量,剩余的奶量,桶的编号
{
    if(k == flag)//如果当前桶数满足
    {
        if(v == 0)//并且牛奶也取空
        {
            memcpy(ans, temp, sizeof(temp));
            find = true;
        }
        return;
    }
    if(s &gt; n || bo[s] &gt; ans[k])//种类超了或者字典序大了就结束
        return;
    temp[k] = bo[s];//记录
    for(int i = 1; i * bo[s] &lt;= v; i++)
    {
        dfs(k + 1, v - i * bo[s], s + 1);//用几个这样的桶
    }
    if(s &lt; n)
        dfs(k, v, s + 1);//不用这个桶
}
int main()
{
    int i;
    gkd();
    cin &gt;&gt; m &gt;&gt; n;
    memset(ans, 2, sizeof(ans));
    for(int i = 1; i &lt;= n; i++)
        cin &gt;&gt; bo[i];
    std::sort(bo + 1, bo + n + 1);
    for(flag = 1; flag &lt;= n; flag++)
    {
        dfs(0, m, 1);
        if(find == true)
            break;
    }
    cout &lt;&lt; flag;
    for(int i = 0; i &lt; flag; i++)
        cout &lt;&lt;" "&lt;&lt; ans[i];
    cout &lt;&lt; '\n';
    return 0;
}
&lt;/code&gt;&lt;/pre&gt;

————————————————————————————————————————————————————————————————————————————

&lt;h3&gt;Luogu 2567 [SCOI2010]幸运数字&lt;/h3&gt;

&lt;h2&gt;题目背景&lt;/h2&gt;

四川NOI省选2010

&lt;h2&gt;题目描述&lt;/h2&gt;

在中国,很多人都把6和8视为是幸运数字!lxhgww也这样认为,于是他定义自己的“幸运号码”是十进制表示中只包含数字6和8的那些号码,比如68,666,888都是“幸运号码”!但是这种“幸运号码”总是太少了,比如在[1,100]的区间内就只有6个(6,8,66,68,86,88),于是他又定义了一种“近似幸运号码”。lxhgww规定,凡是“幸运号码”的倍数都是“近似幸运号码”,当然,任何的“幸运号码”也都是“近似幸运号码”,比如12,16,666都是“近似幸运号码”。

现在lxhgww想知道在一段闭区间[a, b]内,“近似幸运号码”的个数。

&lt;h2&gt;输入格式&lt;/h2&gt;

输入数据是一行,包括2个数字a和b

&lt;h2&gt;输出格式&lt;/h2&gt;

输出数据是一行,包括1个数字,表示在闭区间[a, b]内“近似幸运号码”的个数

&lt;h2&gt;输入输出样例&lt;/h2&gt;

&lt;strong&gt;输入 #1&lt;/strong&gt;复制

&lt;strong&gt;输出 #1&lt;/strong&gt;复制

&lt;h2&gt;说明/提示&lt;/h2&gt;

对于30%的数据,保证1&lt;=a&lt;=b&lt;=1000000

对于100%的数据,保证1&lt;=a&lt;=b&lt;=10000000000

把所有幸运数字找出,把倍数关系的删掉,然后dfs找近似的

```c++
#include<map>
#include<stack>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define int long long
using std::cin;
using std::cout;
void gkd()
{
    std::ios::sync_with_stdio(false);
    cout.tie(NULL);
}

const int maxn = 1e5 + 233;
int te[maxn], fin[maxn], ans, l, r;
bool check[maxn];
const int p = 1e9 + 7;

inline int gcd(int x, int y)
{
    return x % y == 0 ? y : gcd(y, x % y);
}
inline int lcm(int x, int y)
{
    return x / gcd(x, y) * y;
}

int tot, cnt;
inline void pre(long long dep,long long cnt,long long now,long long x)
{
    if(dep&gt;cnt)
    {//预处理的过程
        te[++tot]=now;
        return;
    }
    pre(dep+1,cnt,now+x<em>8,x</em>10);
    pre(dep+1,cnt,now+x<em>6,x</em>10);
}
inline void uniq()
{





<pre><code>for(int i = 1; i &lt;= tot; i++)
    for(int j = 1; j &lt; i; j++)
        if(te[i] % te[j] == 0)
        {
            check[i] = 1;
            break;
        }

}

inline void dfs(int pos, int k, int x)
{//当前位置,是几个数的lcm,现在数字大小
if(x > r)
return;
if(pos > cnt)
{
if(!k)
return;
if(k & 1)
ans += (r / x) - (l / x);
else
ans -= (r / x) - (l / x);
return;
}
dfs(pos + 1, k, x);//不选择当前的数字
int temp = x / gcd(x, fin[pos]);
if( (double)1.0 * temp * fin[pos] > (double)r)
return;
dfs(pos + 1, k + 1, lcm(x, fin[pos]));
}
signed main()
{
gkd();
cin >> l >> r;
for(long long i=1;i<=10;i++)pre(1,i,0,1);
uniq();
for(int i = tot; i >= 1; i--)
if(!check[i])
fin[++cnt] = te[i];
l--;
dfs(1, 0, 1);
cout << ans;
return 0;
}


————————————————————————————————————————————————————————————————————————————

### Luogu1514 引水入城

## 题目描述

在一个遥远的国度,一侧是风景秀美的湖泊,另一侧则是漫无边际的沙漠。该国的行政区划十分特殊,刚好构成一个N行 ×*M* 列的矩形,如上图所示,其中每个格子都代表一座城市,每座城市都有一个海拔高度。

![img](https://cdn.luogu.com.cn/upload/pic/299.png)

为了使居民们都尽可能饮用到清澈的湖水,现在要在某些城市建造水利设施。水利设施有两种,分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。

因此,只有与湖泊毗邻的第11 行的城市可以建造蓄水厂。而输水站的功能则是通过输水管线利用高度落差,将湖水从高处向低处输送。故一座城市能建造输水站的前提,是存在比它海拔更高且拥有公共边的相邻城市,已经建有水利设施。由于第N*N* 行的城市靠近沙漠,是该国的干旱区,所以要求其中的每座城市都建有水利设施。那么,这个要求能否满足呢?如果能,请计算最少建造几个蓄水厂;如果不能,求干旱区中不可能建有水利设施的城市数目。

## 输入格式

每行两个数,之间用一个空格隔开。输入的第一行是两个正整数N,M*N*,*M*,表示矩形的规模。接下来N*N* 行,每行M*M* 个正整数,依次代表每座城市的海拔高度。

## 输出格式

两行。如果能满足要求,输出的第一行是整数11,第二行是一个整数,代表最少建造几个蓄水厂;如果不能满足要求,输出的第一行是整数00,第二行是一个整数,代表有几座干旱区中的城市不可能建有水利设施。

## 输入输出样例

输入 #1

2 5
9 1 5 4 3
8 7 6 1 2


输出 #1

1
1


输入 #2

3 6
8 4 5 6 4 4
7 3 4 3 3 3
3 2 2 1 1 2


输出 #2

1
3


## 说明/提示

【样例1 说明】

只需要在海拔为99 的那座城市中建造蓄水厂,即可满足要求。

【样例2 说明】

![img](https://cdn.luogu.com.cn/upload/pic/300.png)

上图中,在33个粗线框出的城市中建造蓄水厂,可以满足要求。以这33个蓄水厂为源头在干旱区中建造的输水站分别用3 种颜色标出。当然,建造方法可能不唯一。

【数据范围】

![img](https://cdn.luogu.com.cn/upload/pic/301.png)



```c++
#include&lt;map&gt;
#include&lt;stack&gt;
#include&lt;cmath&gt;
#include&lt;queue&gt;
#include&lt;cstdio&gt;
#include&lt;vector&gt;
#include&lt;cstring&gt;
#include&lt;iostream&gt;
#include&lt;algorithm&gt;
inline int gkd()
{
    int ret=0;
    char c=getchar();
    while (c&lt;'0' || c&gt;'9') c=getchar();
    while (c&gt;='0' &amp;&amp; c&lt;='9'){
        ret=ret*10+c-'0';
        c=getchar();
    }
    return ret;
}
const int maxn = 555;
int map[maxn][maxn], vis[maxn][maxn], l[maxn][maxn], r[maxn][maxn];
int n, m, cnt;
int move[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
void dfs(int x, int y)
{
    vis[x][y] = true;
    for(int i = 0; i &lt; 4; i++)
    {
        int nowx = x + move[i][0];
        int nowy = y + move[i][1];
        if(nowx &lt; 1 || nowx &gt; n || nowy &lt; 1 || nowy &gt; m)
            continue;
        if(map[nowx][nowy] &gt;= map[x][y])
            continue;
        if(!vis[nowx][nowy])
            dfs(nowx, nowy);
        l[x][y] = std::min(l[x][y], l[nowx][nowy]);
        r[x][y] = std::max(r[x][y], r[nowx][nowy]);
    }//统计每个覆盖的区间
}
int main()
{
    n = gkd();
    m = gkd();
    memset(vis,false,sizeof(vis));
    memset(l,0x3f,sizeof(l));
    memset(r,0,sizeof(r));
    for(int i = 1; i &lt;= m; i++)
        l[n][i] = r[n][i] = i;

    for(int i = 1; i &lt;= n; i++)
        for(int j = 1; j &lt;= m; j++)
        {
            map[i][j] = gkd();
        }

    for(int i = 1; i &lt;= m; i++)
        if(!vis[1][i])
            dfs(1, i);
    bool flag = 0;
    int cnt = 0;
    for(int i = 1; i &lt;= m; i++)
        if(!vis[n][i])
        {
            flag = 1;
            cnt++;
        }  
    if(flag)//如果有没有被覆盖的
    {
        puts("0");
        printf("%d", cnt);
        return 0;
    }
    int left = 1;
    while(left &lt;= m)//进行线段覆盖
    {
        int right = 0;
        for(int i = 1; i &lt;= m; i++)
            if(l[1][i] &lt;= left)
                right = std::max(right, r[1][i]);
        cnt++;
        left = right + 1;
    }
    puts("1");
    printf("%d", cnt);
}

————————————————————————————————————————————————————————————————————————————

<code class="">

<code class="">