NO.-7

Veröffentlicht am | Edited on

[USACO17JAN]Balanced Photo平衡的照片

题目描述

Farmer John is arranging his NN cows in a line to take a photo (1 \leq N \leq 100,0001≤N≤100,000). The height of the iith cow in sequence is h_ihi, and the heights of all cows are distinct.

As with all photographs of his cows, FJ wants this one to come out looking as nice as possible. He decides that cow ii looks “unbalanced” if L_iLi and R_iRi differ by more than factor of 2, where L_iLi and R_iRi are the number of cows taller than ii on her left and right, respectively. That is, ii is unbalanced if the larger of L_iLi and R_iRi is strictly more than twice the smaller of these two numbers. FJ is hoping that not too many of his cows are unbalanced.

Please help FJ compute the total number of unbalanced cows.

FJ正在安排他的N头奶牛站成一排来拍照。（1<=N<=100,000)序列中的第i头奶牛的高度是h[i]，且序列中所有的奶牛的身高都不同。

就像他的所有牛的照片一样，FJ希望这张照片看上去尽可能好。他认为，如果L[i]和R[i]的数目相差2倍以上的话，第i头奶牛就是不平衡的。（L[i]和R[i]分别代表第i头奶牛左右两边比她高的数量）。FJ不希望他有太多的奶牛不平衡。

请帮助FJ计算不平衡的奶牛数量。

输入输出格式

输入格式：

The first line of input contains NN. The next NN lines contain h_1 \ldots h_Nh1…hN, each a nonnegative integer at most 1,000,000,000.

第一行一个整数N。接下N行包括H[1]到H[n]，每行一个非负整数（不大于1,000，000，000)。

输出格式：

Please output a count of the number of cows that are unbalanced.

请输出不平衡的奶牛数量。

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
8
7
34
6
23
0
5
99
2

输出样例#1：

1
3

题解

统计左边高的和右边高的显然是离散化+树状数组。右边高的就倒着让每头奶牛右边的比它先插入就可以统计了。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 100005
#define lowbit(x) (x & -x)
int bit[maxn] , l[maxn] , r[maxn] , n , tot , rank[maxn] , ans;
struct cow{
    int h , k;
}c[maxn];
 bool operator<(cow x , cow y){return x.h < y.h;}
inline int query(int x)
{
    int ans = 0;
    for(int i = x ; i ; i -= lowbit(i))
        ans += bit[i];
    return ans;
}
inline void update(int x , int v)
{
    for(int i = x ; i <= tot ; i += lowbit(i))
        bit[i] += v;
}
int main()
{
    scanf("%d",&n);
    for(int i = 1 ; i <= n ; ++i)
        scanf("%d",&c[i].h) , c[i].k = i;
    std::sort(c+1,c+n+1);
    c[0].h = 19260817;
    for(int i = 1 ; i <= n ; ++i)
        if(c[i].h == c[i-1].h)
            rank[c[i].k] = tot;
        else rank[c[i].k] = ++ tot;
    // for(int i = 1 ; i <= tot ; ++i)
    //     printf("%d",rank[i]);
    for(int i = 1 ; i <= n ; ++i)
        l[i] = i - 1 - query(rank[i]) , update(rank[i],1);
    std::memset(bit,0,sizeof(bit));
    for(int i = n ; i >= 1 ; --i)
        r[i] = n - i - query(rank[i]) , update(rank[i],1);
    // for(int i = 1 ; i <= n ; ++i)
    //     printf("%d %d\n",l[i],r[i]);
    for(int i = 1 ; i <= n ; ++i)
        if(l[i] > 2 * r[i] || r[i] > 2 * l[i])
            ++ans;
    printf("%d",ans);
}

接下来复习树上背包

树形DP复习完毕。。。

P2014 选课

题目描述

在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有N门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程a是课程b的先修课即只有学完了课程a，才能学习课程b）。一个学生要从这些课程里选择M门课程学习，问他能获得的最大学分是多少？

输入输出格式

输入格式：

第一行有两个整数N,M用空格隔开。(1<=N<=300,1<=M<=300)

接下来的N行,第I+1行包含两个整数ki和si, ki表示第I门课的直接先修课，si表示第I门课的学分。若ki=0表示没有直接先修课（1<=ki<=N, 1<=si<=20）。

输出格式：

只有一行，选M门课程的最大得分。

输入输出样例

输入样例#1：

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

输出样例#1：

1
13

题解

这应该是树上背包最简单的问题了，题意就是让你选k件物品，每种物品选的条件是他的父亲都选，问最大价值。

设
$
f(u,k)
$
表示u的子树内选k件物品的最大价值是多少。

转移只需要抓住

每种物品选的条件是他的父亲都选

这个条件
$
dp[v][k-1]=dp[u][k]+val
$
$
dp[u][k]=max(dp[u][k],dp[v][k−1])
$
这个我想了想它比真正的树上背包是要少一个枚举第二维的，因为它用了贪心的思想，显然根节点选的情况下子树可以选k-1个。

一般来说是这样的
$
f(u,k) = max\{f(v,t) + f(u,k-t-1)\}
$
这个似乎更好理解一点，emmm。

总结一下：树上背包主要就是将每个子树（或者说叫儿子，因为每个儿子的状态更新完后才会更新父亲的状态）看做物品，然后做正常背包，最上面那个是针对权值都是非负的情况的一种优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 305
#define maxm 305
int f[maxn][maxm] , n , head[maxn] , m , val[maxn] , cnt;
struct edge{
    int next , to;
}e[maxn*2];
void dfs(int x , int cnt , int fx)
{
    if(cnt == 0) return;
    for(int i = head[x] ; i ; i = e[i].next)
    {
        int v = e[i].to;
        if(v == fx) continue;
        for(int k = 0 ; k < cnt ; ++k)
            f[v][k] = f[x][k] + val[v];
        dfs(v , cnt - 1 , x);
        for(int k = 1 ; k <= cnt ; ++k)
            f[x][k] = std::max(f[x][k] , f[v][k-1]);
    }
}
inline void add(int x , int y)
{
    e[++cnt].next = head[x];
    e[cnt].to = y;
    head[x] = cnt;
}
int main()
{
    scanf("%d%d",&n,&m);
    int x , y;
    for(int i = 1 ; i <= n; ++i)
        scanf("%d%d",&x,&y) , add(i,x) , add(x,i) , val[i] = y;//the i
    dfs(0,m,0);
    printf("%d",f[0][m]);
}

复习基础dp了，希望联赛别挂基础题。

「一本通 5.1 例 1」石子合并

题目描述

将 n 堆石子绕圆形操场排放，现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。

请编写一个程序，读入堆数 n 及每堆的石子数，并进行如下计算：

  1. 选择一种合并石子的方案，使得做 n−1 次合并得分总和最大。
  2. 选择一种合并石子的方案，使得做 n−1 次合并得分总和最小。

输入格式

输入第一行一个整数 nnn，表示有 nnn 堆石子。

第二行 nnn 个整数，表示每堆石子的数量。

输出格式

输出共两行：

第一行为合并得分总和最小值，

第二行为合并得分总和最大值。

样例

样例输入

1
2
4
4 5 9 4

样例输出

1
2
43
54

数据范围与提示

对于 100% 的数据，有
$
1≤n≤200。
$

题解

经典区间dp

首先假如我们有一个区间合并的最优值，以后转移也只需要他，所以

设f(l,r)表示l~r合并的最大值

每次区间合并的代价是整个区间的石子数加上当前两堆分别独自合并的最优值

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 205
int f[maxn*2][maxn*2] , n , v[maxn*2] , g[maxn*2][maxn*2];
int main()
{
    scanf("%d",&n);
    for(int i = 1 ; i <= n ; ++i)
        scanf("%d",&v[i]) , v[i+n] = v[i];
    for(int i = 1 ; i <= 2 * n ; ++i)
        v[i] += v[i-1];
    // for(int i = n + 1 ; i <= 2 * n ; ++i)
    //     v[i] = v[i-n];
    // std::memset(f,-30,sizeof(f));
    // std::memset(g,30,sizeof(g));
    // for(int i = 1 ; i <= 2 * n ; ++i)
    //     f[i][i] = g[i][i] = 0;
    for(int i = 2 ; i <= n ; ++i)
        for(int j = 1 ; j <= 2 * n - i + 1 ; ++j)
        {
            int to = i + j - 1;
            f[j][to] = 0;
            g[j][to] = 0x7ffffff/8;
            for(int k = j ; k < to ; ++k)
            {
                f[j][to] = std::max(f[j][to] , f[j][k] + f[k+1][to]);
                g[j][to] = std::min(g[j][to] , g[j][k] + g[k+1][to]);
            }
            g[j][to] += v[to] - v[j-1];
            f[j][to] += v[to] - v[j-1];
        }
    int ans1 = 0 , ans2 = 0x7fffffff;
    for(int i = 1 ; i <= n ; ++i)
        ans1 = std::max(ans1 , f[i][i+n-1]) , ans2 = std::min(ans2 , g[i][i+n-1]);
    printf("%d%d",ans2 , ans1);
}

[USACO06NOV]路障Roadblocks

题目描述

Bessie has moved to a small farm and sometimes enjoys returning to visit one of her best friends. She does not want to get to her old home too quickly, because she likes the scenery along the way. She has decided to take the second-shortest rather than the shortest path. She knows there must be some second-shortest path.

The countryside consists of R (1 ≤ R ≤ 100,000) bidirectional roads, each linking two of the N (1 ≤ N ≤ 5000) intersections, conveniently numbered 1..N. Bessie starts at intersection 1, and her friend (the destination) is at intersection N.

The second-shortest path may share roads with any of the shortest paths, and it may backtrack i.e., use the same road or intersection more than once. The second-shortest path is the shortest path whose length is longer than the shortest path(s) (i.e., if two or more shortest paths exist, the second-shortest path is the one whose length is longer than those but no longer than any other path).

贝茜把家搬到了一个小农场，但她常常回到FJ的农场去拜访她的朋友。贝茜很喜欢路边的风景，不想那么快地结束她的旅途，于是她每次回农场，都会选择第二短的路径，而不象我们所习惯的那样，选择最短路。 贝茜所在的乡村有R(1<=R<=100,000)条双向道路，每条路都联结了所有的N(1<=N<=5000)个农场中的某两个。贝茜居住在农场1，她的朋友们居住在农场N（即贝茜每次旅行的目的地）。 贝茜选择的第二短的路径中，可以包含任何一条在最短路中出现的道路，并且，一条路可以重复走多次。当然咯，第二短路的长度必须严格大于最短路（可能有多条）的长度，但它的长度必须不大于所有除最短路外的路径的长度。

输入输出格式

输入格式：

Line 1: Two space-separated integers: N and R

Lines 2..R+1: Each line contains three space-separated integers: A, B, and D that describe a road that connects intersections A and B and has length D (1 ≤ D ≤ 5000)

输出格式：

Line 1: The length of the second shortest path between node 1 and node N

输入输出样例

输入样例#1：

1
2
3
4
5
4 4
1 2 100
2 4 200
2 3 250
3 4 100

输出样例#1：

1
450

说明

Two routes: 1 -> 2 -> 4 (length 100+200=300) and 1 -> 2 -> 3 -> 4 (length 100+250+100=450)

题解

虽然现在最短路我已经倾向于写Dijkstra，但是这种灵活的最短路变形问题还是SPFA好思考一点。

题目要求严格非简单次短路，SPFA的更新方法很好想。

假如当前点u的最短路可以更新v的最短路，更新并且v的次短路变为原来的最短路。

假如当前点u的最短路不能更新v的最短路，但是可以更新v的次短路也要更新。

u的次短路也可以试着更新v的次短路。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#define maxn 5005
#define maxm 100005
int head[maxn] , cnt , n , m , d[maxn] , g[maxn];
bool vis[maxn];
struct edge{
    int next , to , dis;
}e[maxm*2];
inline void add(int x,  int y , int dis)
{
    e[++cnt].next = head[x];
    e[cnt].to = y;
    e[cnt].dis = dis;
    head[x] = cnt;
}
void SPFA(int s)
{
    std::queue<int> q;
    std::memset(d,0x7f,sizeof(d));
    std::memset(g,0x7f , sizeof(g));
    d[s] = 0;
    q.push(s) , vis[s] = true;
    while(!q.empty())
    {
        int k = q.front();
        q.pop();
        vis[k] = false;
        for(int i = head[k] ; i ; i = e[i].next)
        {
            if(d[k] + e[i].dis < d[e[i].to])
            {
                g[e[i].to] = d[e[i].to];
                d[e[i].to] = d[k] + e[i].dis;
                if(!vis[e[i].to])   q.push(e[i].to) , vis[e[i].to] = true;
            }
            if(d[k] + e[i].dis > d[e[i].to] && d[k] + e[i].dis < g[e[i].to])
            {
                g[e[i].to] = d[k] + e[i].dis;
                if(!vis[e[i].to])   q.push(e[i].to) , vis[e[i].to] = true;
            }
            if(g[k] + e[i].dis < g[e[i].to])
            {
                g[e[i].to] = g[k] + e[i].dis;
                if(!vis[e[i].to])   q.push(e[i].to) , vis[e[i].to] = true;
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    int x , y , dis;
    for(int i = 1 ; i <= m ; ++i)
        scanf("%d%d%d",&x,&y,&dis) , add(x,y,dis) , add(y,x,dis);
    SPFA(1);
    printf("%d",g[n]);
}

第六讲 分组的背包问题

问题

有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

算法

这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设f[k][v]表示前k组物品花费费用v能取得的最大权值，则有：

1
2
> f[k][v]=max{f[k-1][v],f[k-1][v-c[i]]+w[i]|物品i属于组k}
>

使用一维数组的伪代码如下：

1
2
3
4
for 所有的组k
    for v=V..0
        for 所有的i属于组k
            f[v]=max{f[v],f[v-c[i]]+w[i]}

注意这里的三层循环的顺序，甚至在本文的第一个beta版中我自己都写错了。“for v=V..0”这一层循环必须在“for 所有的i属于组k”之外。这样才能保证每一组内的物品最多只有一个会被添加到背包中。（同01背包与完全背包）

另外，显然可以对每组内的物品应用P02中“一个简单有效的优化”。

小结

分组的背包问题将彼此互斥的若干物品称为一个组，这建立了一个很好的模型。不少背包问题的变形都可以转化为分组的背包问题（例如P07），由分组的背包问题进一步可定义“泛化物品”的概念，十分有利于解题。

相信理解了这个之后，对于树上背包的解决思路有了更加深刻的认识。

来看一道树上背包的简单题

二叉苹果树

题目描述

有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）

这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。

我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树

1
2
3
4
5
2   5
 \ / 
  3   4
   \ /
    1

现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。

给定需要保留的树枝数量，求出最多能留住多少苹果。

输入输出格式

输入格式：

第1行2个数，N和Q(1<=Q<= N,1<N<=100)。

N表示树的结点数，Q表示要保留的树枝数量。接下来N-1行描述树枝的信息。

每行3个整数，前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。

每根树枝上的苹果不超过30000个。

输出格式：

一个数，最多能留住的苹果的数量。

输入输出样例

输入样例#1：

1
2
3
4
5
5 2
1 3 1
1 4 10
2 3 20
3 5 20

输出样例#1：

1
21

题解

显然每颗子树的每个状态是一件物品， 每颗子树的所有状态构成一组物品，每组物品只能选一件，使当前状态值最大 = 分组背包

注意边界问题，不合法的边界将会导致错误

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 105
int f[maxn][maxn] , n , q , head[maxn] , cnt , v[maxn] , sz[maxn];
struct edge{
    int next , to , dis;
}e[maxn*2];
inline void add(int x, int y , int dis)
{
    e[++cnt].next = head[x];
    e[cnt].to = y;
    e[cnt].dis = dis;
    head[x] = cnt;
}
void pre(int x , int fx , int d)
{
    v[x] = d;
    for(int i = head[x] ; i ; i = e[i].next)
        if(e[i].to != fx)
            pre(e[i].to , x , e[i].dis);
}
void dfs(int x , int fx)
{
    for(int i = head[x] ; i ; i = e[i].next)
        if(e[i].to != fx)
        {
            dfs(e[i].to , x);
            sz[x] += sz[e[i].to] + 1;
            for(int j = std::min(q,sz[x]); j >= 1 ; --j)
                for(int k = std::min(j-1,sz[e[i].to]) ; k >= 0 ; --k)
                    f[x][j] = std::max(f[e[i].to][k] + f[x][j-k-1] + e[i].dis , f[x][j]);
        }
        // for(int i = q ; i >= 1 ; --i)
        //     f[x][i] = f[x][i-1] + v[x];

}
int main()
{
    scanf("%d%d",&n,&q);
    int x , y , dis;
    for(int i = 1 ; i <= n-1 ; ++i)
        scanf("%d%d%d",&x,&y,&dis) , add(x,y,dis) , add(y,x,dis);
    pre(1,1,0);
    dfs(1,1);
    printf("%d",f[1][q]);
}