bef-> NO.15

Veröffentlicht am

序列sequence

题目描述

给定一个序列，每次操作可以把某个数+1-1。要求把序列变成非降数列。而且要求修改后的数列只能出现修改前的数。

输入输出格式

输入格式：

第一行输入一个n，表示有n

个数字。第二行输入n个整数，整数的绝对值不超过

输出格式：

输出一个数，表示最少的操作次数

输入输出样例

输入样例#1：

1
2
5
3 2 -1 2 11

输出样例#1：

1
4

输入样例#2：

1
2
5
2 1 1 1 1

输出样例#2：

1
1

题解

这道题的定位是高难度贪心，事实上是我见过的最难的贪心之一。

这道题现在想来分析出来不是很难

不难看出，y减小的越多，后面的序列越容易变成非降，那么只要让yy减小到xx就好了

看到这里，我一直有一个疑问，如果令yy减小到xx之后，序列不满足非降了怎么办？

仔细想了想，实际上应该是这样的：为了让序列非降，y不能小于y之前的最大值。而由于y是整个序列的最大值，如果它之前的最大值zz小于等于xx，那么将y减小到x仍能保证序列是非降的。否则的话，z大于x小于y，仍是在区间[x,y][x,y]内，那么移动的代价是y-x，所以用于更新答案是没有问题的

那么这里为什么要让y减到最小呢？这是因为x和y不论如何调整，他们的代价之和都已经不变了，但问题是他们目前选的最优方案并不是之后的最优。为了满足他们在之后最优，只有把y减小到x，才能保证之后更有可能非降。

概括一下，对于当前的数，无论最优解如何，对答案的贡献是一定的。而为了保证之后的解也最优，令y减小到x，可以保证之后的解最优，且不会影响当前的最优解

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

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;

int n;
long long ans;
priority_queue<int> q;

int main() {
    scanf("%d",&n);
    for(int i = 1; i <= n; i++)
    {
        int num;
        scanf("%d",&num);
        q.push(num);
        if(num < q.top()) 
        {
            ans += q.top() - num;
            q.pop();
            q.push(num);
        }
    }
    printf("%lld\n", ans);
}

差分约束系统

今天开始刷一遍一本通提高篇，看到了图论的这个东西。

简单来说是求解一系列线性变量差值不等式的方法，因为和最短路的三角形不等式原理一样，我们就可以通过建立图论模型，用最短路求解。

一、何为差分约束系统：

差分约束系统（system of difference constraints），是求解关于一组变数的特殊不等式组之方法。如果一个系统由n个变量和m个约束条件组成，其中每个约束条件形如xj-xi<=bk(i,j∈[1,n],k∈[1,m]),则称其为差分约束系统(system of difference constraints)。亦即，差分约束系统是求解关于一组变量的特殊不等式组的方法。

通俗一点地说，差分约束系统就是一些不等式的组，而我们的目标是通过给定的约束不等式组求出最大值或者最小值或者差分约束系统是否有解。

二、差分约束系统的求解：

差分约束系统可以转化为图论来解决，对应于上面的不等式组，如果要求出x3-x0的最大值的话，叠加不等式可以推导出x3-x0<=7,最大值即为7，我们可以通过建立一个图，包含6个顶点，对每个xj-xi<=bk，建立一条i到j的有向边，权值为bk。通过求出这个图的x0到x3的最短路可以知道也为7，这是巧合吗？并不是。

之所以差分约束系统可以通过图论的最短路来解，是因为xj-xi<=bk，会发现它类似最短路中的三角不等式d[v] <=d[u]+w[u,v]，即d[v]-d[u]<=w[u,v]。而求取最大值的过程类似于最短路算法中的松弛过程。

三角不等式：（在此引用大牛的博客）

B - A <= c (1)

C - B <= a (2)

C - A <= b (3)

如果要求C-A的最大值，可以知道max（C-A）= min(b,a+c),而这正对应了下图中C到A的最短路。

img

因此，对三角不等式加以推广，变量n个，不等式m个，要求xn-x1的最大值，便就是求取建图后的最短路。

同样地，如果要求取差分约束系统中xn-x1的最小值，便是求取建图后的最长路。最长路可以通过spfa求出来，只需要改下松弛的方向即可，即if(d[v] < d[u] + dist(u,v)) d[v] = d[u] + dist(u,v)。当然我们可以把图中所有的边权取负，求取最短路，两者是等价的。

最长路求解算法证明如下：

最后一点，建图后不一定存在最短路/最长路，因为可能存在无限减小/增大的负环/正环，题目一般会对应于不同的输出。判断差分约束系统是否存在解一般判环即可。

注意不能用DIJ算法，只能用死去的SPFA或者Bellman-Ford

Interval

Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 30524 Accepted: 11834

Description

You are given n closed, integer intervals [ai, bi] and n integers c1, …, cn.
Write a program that:
reads the number of intervals, their end points and integers c1, …, cn from the standard input,
computes the minimal size of a set Z of integers which has at least ci common elements with interval [ai, bi], for each i=1,2,…,n,
writes the answer to the standard output.

Input

The first line of the input contains an integer n (1 <= n <= 50000) — the number of intervals. The following n lines describe the intervals. The (i+1)-th line of the input contains three integers ai, bi and ci separated by single spaces and such that 0 <= ai <= bi <= 50000 and 1 <= ci <= bi - ai+1.

Output

The output contains exactly one integer equal to the minimal size of set Z sharing at least ci elements with interval [ai, bi], for each i=1,2,…,n.

Sample Input

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

Sample Output

1
6

题解

差分约束求解即可，注意隐含条件比如每个数只能选一次或者前i+1个数选的一定比i个多这种。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <cstring>
#include <iostream>
#define maxn 50005
int head[maxn] , cnt , n , s , t , d[maxn];
bool inq[maxn];
struct edge{
    int next ,to , dis;
}e[maxn * 10];
inline void add(int x , int y , int d)
{
    e[++cnt].next = head[x];
    e[cnt].to = y;
    e[cnt].dis = d;
    head[x] = cnt;
}
inline void SPFA(int s)
{
    std::queue<int> q;
    for(int i = s ; i <= t ; ++i)
        d[i] = -0x7ffffff;
    d[s] = 0;
    q.push(s);
    inq[s] = true;
    while(!q.empty())
    {
        int k = q.front();
        q.pop();
        inq[k] = false;
        for(int i = head[k] ; i ; i = e[i].next)
        {
            if(d[k] + e[i].dis > d[e[i].to])
            {
                d[e[i].to] = d[k] + e[i].dis;
                if(!inq[e[i].to])
                    q.push(e[i].to) , inq[e[i].to] = true;
            }
        }
    }
}
int main()
{
    scanf("%d",&n);
    int x , y , dd;
    for(int i = 1; i <= n ; ++i)
    {
        scanf("%d%d%d",&x,&y,&dd);
        add(x-1,y,dd) , s = std::min(x-1,s) , t = std::max(t,y);
    }
    for(int i = s ; i <= t ; ++i)
    {
        add(i,i+1,0);
        add(i+1,i,-1);
    }
    SPFA(s);
    printf("%d",d[t]);
}

[Wind Festival]Running In The Sky

题目背景

[Night - 20:02[Night−20:02 P.M.]P.M.]

夜空真美啊……但是……快要结束了呢……

题目描述

一天的活动过后，所有学生都停下来欣赏夜空下点亮的风筝。CurtisCurtis NishikinoNishikino想要以更近的视角感受一下，所以她跑到空中的风筝上去了(这对于一个妹子来说有点匪夷所思)! 每只风筝上的灯光都有一个亮度 k_iki. 由于风的作用，一些风筝缠在了一起。但是这并不会破坏美妙的气氛，缠在一起的风筝会将灯光汇聚起来，形成更亮的光源！

CurtisCurtis NishikinoNishikino已经知道了一些风筝间的关系，比如给出一对风筝(a,b)(a,b), 这意味着她可以从 aa 跑到 bb 上去，但是不能返回。

现在，请帮她找到一条路径(她可以到达一只风筝多次，但只在第一次到达时她会去感受上面的灯光), 使得她可以感受到最多的光亮。同时请告诉她这条路径上单只风筝的最大亮度，如果有多条符合条件的路径，输出能产生最大单只风筝亮度的答案。

输入输出格式

输入格式：

第一行两个整数 nn 和 mm. nn 是风筝的数量, mm 是风筝间关系对的数量.

接下来一行 nn 个整数 k_iki.

接下来 mm 行, 每行两个整数 aa 和 bb, 即CurtisCurtis可以从 aa 跑到 bb.

输出格式：

一行两个整数。CurtisCurtis在计算出的路径上感受到的亮度和，这条路径上的单只风筝最大亮度.

输入输出样例

输入样例#1：

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

输出样例#1：

1
41 11

说明

对于 20% 的数据,

对于 80\%的数据,

对于 100% 的数据,

题解

理解了题意不难想到是

Tarjan缩点 + DAGDP

然后一交80，仔细重读了题发现是最大单只风筝亮度而不是缩在一起，而且最大单只风筝亮度指的是最大路径亮度和的路径上的最大单只风筝，以后审题能力还是要加强。

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <stack>
#include <queue>
#include <map>
#define maxn 200005
#define maxm 500005
int head[maxn] , cnt , val[maxn] , v[maxn] , tot , low[maxn] , dfn[maxn] , n , idx , scc[maxn] , f[maxn] , g[maxn] ,d[maxn] , m , h[maxn];
std::stack<int> st;
std::map<long long int , int>  vis[maxn];
bool ins[maxn];
struct edge{
    int next , to;
}e[maxm] ;
struct E{
    int f , t;
}er[maxm];
inline void add(int x , int y)
{
    e[++cnt].next = head[x];
    e[cnt].to = y;
    head[x] = cnt;
    ++ d[y];
}
void Tarjan(int x)
{
    dfn[x] = low[x] = ++idx;
    st.push(x);
    ins[x] = true;
    for(int i = head[x] ; i ; i = e[i].next)
    {
        if(!dfn[e[i].to])
        {
            Tarjan(e[i].to);
            low[x] = std::min(low[x] , low[e[i].to]);
        }
        else if(ins[e[i].to])   low[x] = std::min(low[x] , dfn[e[i].to]);
    }
    if(dfn[x] == low[x])
    {
        ++tot;
        while(st.top() != x)
        {
            scc[st.top()] = tot;
            ins[st.top()] = false;
            v[tot] += val[st.top()];
            g[tot] = std::max(g[tot] , val[st.top()]);
            // printf("%d : %d",tot , st.top());
            st.pop();
        }
        scc[st.top()] = tot;
        ins[st.top()] = false;
        v[tot] += val[st.top()];
        // printf("%d : %d",tot , st.top());
        g[tot] = std::max(g[tot] , val[st.top()]);
        st.pop();
    }
}
inline void DAGDP()
{
    std::queue<int> q;
    for(int i = 1 ; i <= tot ; ++i)
        if(!d[i])   q.push(i) , f[i] = v[i];
    for(int i = 1 ; i <= tot ; ++i)
        h[i] = g[i];
    while(!q.empty())
    {
        int k = q.front();
        q.pop();
        for(int i = head[k] ; i ; i = e[i].next)
        {
            if(v[e[i].to] + f[k] > f[e[i].to])
            {
                f[e[i].to] = std::max(f[e[i].to] , v[e[i].to] + f[k]);
                g[e[i].to] = std::max(h[e[i].to] , g[k]);
            }
            else if(v[e[i].to] + f[k] == f[e[i].to])    g[e[i].to] = std::max(g[e[i].to] , g[k]);
            --d[e[i].to];
            if(!d[e[i].to]) q.push(e[i].to);
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1 ; i <= n ; ++i)
        scanf("%d",&val[i]);
    int x , y;
    int gar = 0;
    for(int i = 1 ; i <= m ; ++i)
        scanf("%d%d",&x,&y) , add(x,y) , er[++gar].f = x , er[gar].t = y;
    // puts("OK");
    for(int i = 1 ; i <= n ; ++i)
    {
        if(dfn[i])  continue;
        Tarjan(i);
    }
    // puts("OK");
    std::memset(head,0,sizeof(head));
    std::memset(e,0,sizeof(e));
    std::memset(d,0,sizeof(d));
    cnt = 0;
    for(int i = 1 ; i <= m ; ++i)
    {
        int u = er[i].f , v = er[i].t;
        if(scc[u] != scc[v])
            if(!vis[scc[u]][scc[v]])
                add(scc[u],scc[v]) , vis[scc[u]][scc[v]] = 1;
    }
    DAGDP();
    int ans1 = -515454575 , ans2 = -135453445;
    for(int i = 1 ; i <= n ; ++i)
        if(f[i] > ans1)
            ans1 = f[i] , ans2 = g[i];
        else if(f[i] == ans1) ans2 = std::max(ans2 , g[i]);
    printf("%d %d",ans1,ans2);
}

【模板】缩ecc查询两点距离

题意

如题

数据范围

题解

算法如题所述

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <stack>
#include <cstring>
#define maxn 100005
#define maxm 300005
int head[maxn] , cnt , idx , n , m , x , y , tot , v[maxn] , dfn[maxn] , low[maxn] , ecc[maxn] , f[maxn][22] , dep[maxn] , lg[maxn];
bool bri[maxm * 2];
struct edge{
    int next , to;
}e[maxm*2];
struct E{
    int f , t;
}ed[maxm*2];
std::stack<int> st;
void Tarjan(int x , int fx)
{
    dfn[x] = low[x] = ++idx;
    st.push(x);
    for(int i = head[x] ; i ; i = e[i].next)
    {
        if(!dfn[e[i].to])
        {
            // printf("Tarjan! %d -> %d\n",x,e[i].to);
            Tarjan(e[i].to , x);
            low[x] = std::min(low[x] , low[e[i].to]);
            // printf("Node %d -> low : %d dfn -> %d\n",x,low[x],dfn[x]);
        }
        else if(e[i].to != fx) low[x] = std::min(low[x] , dfn[e[i].to]);
    }
    if(low[x] == dfn[x])
    {
        ++tot;
        // printf("the %dth vcc! :\n",tot);
        while(st.top() != x)
        {
            ecc[st.top()] = tot;
            // printf("%d ",st.top());
            st.pop();
        }
        // printf("%d\n",st.top());
        ecc[st.top()] = tot;
        st.pop();
    }
}
inline void add(int x , int y)
{
    e[++cnt].next = head[x];
    e[cnt].to = y;
    head[x] = cnt;
}
inline void write(int x)
{
    if(!x)  return;
    write(x/2);
    putchar((x&1)+48);
}
void dfs(int x , int fx)
{
    f[x][0] = fx;
    dep[x] = dep[fx] + 1;
    dfn[x] = ++idx;
    for(int i = head[x] ; i ; i = e[i].next)
        if(e[i].to != fx)
            dfs(e[i].to , x);
}
inline void OPTI()
{
    for(int i = 1 ; i <= n ; ++i)
        lg[i] = lg[i-1] + (1<<lg[i-1] == i);
    for(int j = 1 ; j <= 20 ; ++j)
        for(int i = 1 ; i <= n ; ++i)
            f[i][j] = f[f[i][j-1]][j-1];
}
inline int LCA(int x , int y)
{
    if(dep[x] < dep[y]) std::swap(x,y);
    while(dep[x] > dep[y])
        x = f[x][lg[dep[x]-dep[y]]-1];
    if(x == y) return x;
    for(int i = dep[x] ; i >= 0 ; --i)
        if(f[x][i] != f[y][i])
            x = f[x][i] , y = f[y][i];
    return f[x][0];
}
int main()
{
    scanf("%d%d",&n,&m);
    int tmp = 0;
    for(int i = 1; i <= m ; ++i)
        scanf("%d%d",&x,&y) , add(x,y) , add(y,x) , ed[++tmp].f = x , ed[tmp].t = y , ed[++tmp].f = y , ed[tmp].t = x;
    Tarjan(1,0);
    std::memset(head,0,sizeof(head));
    std::memset(e,0,sizeof(e));
    cnt = 0;
    // for(int i = 1 ; i <= n ; ++i)
    //     printf("%d ",ecc[i]);
    for(int i = 1 ; i <= 2 * m ; ++i)
        if(ecc[ed[i].f] != ecc[ed[i].t])
            add(ecc[ed[i].f] , ecc[ed[i].t]) ;
    std::memset(dfn,0,sizeof(dfn));
    idx = 0;
    for(int i = 1 ; i <= n ; ++i)
        if(!dfn[i])
            dfs(i,i);
    OPTI();
    int q;
    scanf("%d",&q);
    for(int i = 1 ; i <= q ; ++i)
    {
        scanf("%d%d",&x,&y) ;
        // if(find(x) != find(y))  {puts("10") ; continue;}
        write(dep[ecc[x]] + dep[ecc[y]] - dep[LCA(ecc[x],ecc[y])] * 2 + 1) , putchar(10);
    }

}

[USACO07NOV]防晒霜Sunscreen

题目描述

To avoid unsightly burns while tanning, each of the C (1 ≤ C ≤ 2500) cows must cover her hide with sunscreen when they’re at the beach. Cow i has a minimum and maximum SPF rating (1 ≤ minSPFi ≤ 1,000; minSPFi ≤ maxSPFi ≤ 1,000) that will work. If the SPF rating is too low, the cow suffers sunburn; if the SPF rating is too high, the cow doesn’t tan at all……..

The cows have a picnic basket with L (1 ≤ L ≤ 2500) bottles of sunscreen lotion, each bottle i with an SPF rating SPFi (1 ≤ SPFi ≤ 1,000). Lotion bottle i can cover coveri cows with lotion. A cow may lotion from only one bottle.

What is the maximum number of cows that can protect themselves while tanning given the available lotions?

有C个奶牛去晒太阳 (1 <=C <= 2500)，每个奶牛各自能够忍受的阳光强度有一个最小值和一个最大值，太大就晒伤了，太小奶牛没感觉。

而刚开始的阳光的强度非常大，奶牛都承受不住，然后奶牛就得涂抹防晒霜，防晒霜的作用是让阳光照在身上的阳光强度固定为某个值。

那么为了不让奶牛烫伤，又不会没有效果。

给出了L种防晒霜。每种的数量和固定的阳光强度也给出来了

每个奶牛只能抹一瓶防晒霜，最后问能够享受晒太阳的奶牛有几个。

输入输出格式

输入格式：

* Line 1: Two space-separated integers: C and L

* Lines 2..C+1: Line i describes cow i’s lotion requires with two integers: minSPFi and maxSPFi

* Lines C+2..C+L+1: Line i+C+1 describes a sunscreen lotion bottle i with space-separated integers: SPFi and coveri

输出格式：

A single line with an integer that is the maximum number of cows that can be protected while tanning

输入输出样例

输入样例#1：

1
2
3
4
5
6
3 2
3 10
2 5
1 5
6 2
4 1

输出样例#1：

1
2

题解

一道贪心的基础题。

奶牛看成区间就可以了，防晒霜看成点，我们要尽可能多的用点卡区间，每个点用的次数有限。

于是我们按照左端点排序，然后发现怎么贪心都会被自己随便Hack爆炸。

于是很容易想到按右端点升序排序，然后点按照升序排序 ，然后惊喜的发现满足了严苛的贪心子问题无后效性。

因为当前枚举的这头牛能找到可以用的，后面的牛由于右端点更靠后，防晒霜更有可能满足需求。又右端点相同的左端点小的在前更能物尽其用。

贪心一定要勇于尝试然后尽力证明qwq。

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
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <iostream>
#define maxn 100005
struct Cow{
    int l , r;
}c[maxn];
inline bool operator < (Cow x , Cow y)
{
    if(x.r == y.r) return x.l < y.l;
    return x.r < y.r;
}
struct Pr{
    int v , k ;
}p[maxn];
inline bool operator < (Pr x , Pr y){return x.v < y.v;}
int n , m , ans;
int main()
{
    // freopen("Sun.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i = 1 ; i <= n ; ++i)
        scanf("%d%d",&c[i].l,&c[i].r);
    for(int i = 1 ; i <= m ; ++i)
        scanf("%d%d",&p[i].v,&p[i].k);
    std::sort(c+1,c+n+1);
    std::sort(p+1,p+m+1);
    // for(int i = 1 ; i <= n ; ++i)
    //     printf("%d %d\n",c[i].l,c[i].r);
    // putchar(10);
    // for(int i = 1 ; i <= m ; ++i)
    //     printf("%d %d\n",p[i].v, p[i].k);
    for(int i = 1 ; i <= n ; ++i)
    {
        for(int j = 1 ; j <= m ; ++j)
            if(p[j].k && c[i].l <= p[j].v && c[i].r >= p[j].v)
            {
                --p[j].k , ++ans;
                break;
            }
        // printf("%d %d\n",i,get);
    }
    printf("%d",ans);
}

CF467C George and Job

题目描述

新款手机 iTone6 近期上市，George 很想买一只。不幸地，George 没有足够的钱，所以 George 打算当一名程序猿去打工。现在George遇到了一个问题。 给出一组有 nn 个整数的数列 p_1,p_2,…,p_np1,p2,…,pn ,你需要挑出 kk 组长度为 mm的数，要求这些数互不重叠 即[l_{1},r_{1}],[l_{2},r_{2}],…,[l_{k},r_{k}] (1<=l_{1}<=r_{1}<l_{2}<=r_{2}<…<l_{k}<=r_{k}<=n; r_{i}-l_{i}+1=m)[l1,r1],[l2,r2],…,lk,rk 使选出的数的和值最大，请你帮助George码出这份代码

输入输出格式

输入格式

第1行读入3个整数 n , m , k(1\leq(m×k)\leq n\leq5000) (1\leq(m×k)\leq n\leq5000)n,m,k(1≤(m×k)≤n≤5000)(1≤(m×k)≤n≤5000), 第2行读入 nn 个数 p_1,p_2,…,p_np1,p2,…,pn

输出格式

输出1个整数，代表可以取到的最大值

输入输出样例

如原版 translated by @Venus

题目描述

The new ITone 6 has been released recently and George got really keen to buy it. Unfortunately, he didn’t have enough money, so George was going to work as a programmer. Now he faced the following problem at the work.

Given a sequence of nn integers

. You are to choose kk pairs of integers:

in such a way that the value of sum img is maximal possible. Help George to cope with the task.

输入输出格式

输入格式：

The first line contains three integers nn , mm and kk (1<=(m×k)<=n<=5000)(1<=(m×k)<=n<=5000) . The second line contains nn integers p_{1},p_{2},…,p_{n}p1,p2,…,pn (0<=p_{i}<=10^{9})(0<=pi<=109) .

输出格式：

Print an integer in a single line — the maximum possible value of sum.

输入输出样例

输入样例#1：

1
2
5 2 1
1 2 3 4 5

输出样例#1：

1
9

输入样例#2：

1
2
7 1 3
2 10 7 18 5 33 0

输出样例#2：

1
61

题解

一开始以为能暴力前缀和，后来想了想k小的话随便卡。

然后就是DP.

显然状态是

表示前i个数选j个区间的最大值。

由于题意说区间不能重叠，那对于每个数来说要么不选，要么和前m-1个数构成新区间。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 5005
#define int long long
int n , A[maxn] , s[maxn] , m , k , f[maxn][maxn];
signed main()
{
    scanf("%I64d%I64d%I64d",&n,&m,&k);
    for(int i = 1 ; i <= n ; ++i)
        scanf("%d",&A[i]);
    for(int i = 1 ; i <= n ; ++i)
        s[i] = s[i-1] + A[i];
    // f[m][1] = s[m];
    for(int j = 1 ; j <= k ; ++j)
        for(int i = 1; i <= n ; ++i)
        {
            if(j*m > n) f[i][j] = 0;
            else f[i][j] = std::max(f[i-1][j] , f[std::max(i-m,0*1ll)][j-1] + (s[i] - s[std::max(i-m,0*1ll)]));
        }
    printf("%I64d",f[n][k]);
}

一开始各种边界和负下标问题。

CF191C Fools and Roads

题目描述

有一颗 n个节点的树，kk 次旅行，问每一条边被走过的次数。

输入格式

第一行一个整数 n

接下来 n-1 行，每行两个正整数 x,y

，表示 x 与 y 之间有一条连边。

接下来一个整数 k

接下来 k 行，每行两个正整数 x,y

，表示有一个从 x 到 y 的旅行。

输出格式

总共 n-1 行，按输入顺序输出每条边被走过的次数。

Translated by @larryzhong

题目描述

They say that Berland has exactly two problems, fools and roads. Besides, Berland has nn cities, populated by the fools and connected by the roads. All Berland roads are bidirectional. As there are many fools in Berland, between each pair of cities there is a path (or else the fools would get upset). Also, between each pair of cities there is no more than one simple path (or else the fools would get lost).

But that is not the end of Berland’s special features. In this country fools sometimes visit each other and thus spoil the roads. The fools aren’t very smart, so they always use only the simple paths.

A simple path is the path which goes through every Berland city not more than once.

The Berland government knows the paths which the fools use. Help the government count for each road, how many distinct fools can go on it.

Note how the fools’ paths are given in the input.

输入输出格式

输入格式：

The first line contains a single integer nn ( 2<=n<=10^{5}2<=n<=105 ) — the number of cities.

Each of the next n-1n−1 lines contains two space-separated integers u_{i},v_{i}ui,vi ( 1<=u_{i},v_{i}<=n1<=ui,vi<=n , u_{i}≠v_{i}ui≠vi ), that means that there is a road connecting cities u_{i}ui and v_{i}vi .

The next line contains integer kk ( 0<=k<=10^{5}0<=k<=105 ) — the number of pairs of fools who visit each other.

Next kk lines contain two space-separated numbers. The ii -th line (i>0)(i>0) contains numbers a_{i},b_{i}ai,bi ( 1<=a_{i},b_{i}<=n1<=ai,bi<=n ). That means that the fool number 2i-12i−1 lives in city a_{i}ai and visits the fool number 2i2i , who lives in city b_{i}bi . The given pairs describe simple paths, because between every pair of cities there is only one simple path.

输出格式：

Print n-1n−1 integer. The integers should be separated by spaces. The ii -th number should equal the number of fools who can go on the ii -th road. The roads are numbered starting from one in the order, in which they occur in the input.

输入输出样例

输入样例#1：

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

输出样例#1：

1
2 1 1 1

输入样例#2：

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

输出样例#2：

1
3 1 1 1

说明

In the first sample the fool number one goes on the first and third road and the fool number 3 goes on the second, first and fourth ones.

In the second sample, the fools number 1, 3 and 5 go on the first road, the fool number 5 will go on the second road, on the third road goes the fool number 3, and on the fourth one goes fool number 1

题解

一道树上边权差分的模板题，让每个根对应连向它父亲的边，然后边权差分

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
64
65
66
67
68
69
70
71
72
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 200005
int head[maxn] , cnt , n , c[maxn] ,  dep[maxn] , f[maxn][25] , q , tot , lg[maxn];
struct edge{
    int next , to;
}e[maxn * 2];
struct E{
    int from , to;
}ed[maxn*2];
void dfs(int x , int fx)
{
    f[x][0] = fx;
    dep[x] = dep[fx] + 1;
    for(int i = head[x] ; i ; i = e[i].next)
        if(e[i].to != fx)
            dfs(e[i].to , x);
}
inline void add(int x, int y)
{
    e[++cnt].next = head[x];
    e[cnt].to = y;
    head[x] = cnt;
}
inline void OPTI()
{
    for(int i = 1 ; i <= n ; ++i)
        lg[i] = lg[i-1] + (1<<lg[i-1]==i);
    for(int j = 1 ; j <= 23 ; ++j)
        for(int i = 1 ; i <= n ; ++i)
            f[i][j] = f[f[i][j-1]][j-1];
}
inline int LCA(int x , int y)
{
    if(dep[x] < dep[y]) std::swap(x,y);
    while(dep[x] > dep[y])
        x = f[x][lg[dep[x]-dep[y]]-1];
    if(x == y) return x;
    for(int i = lg[dep[x]] ; i >= 0 ; --i)
        if(f[x][i] != f[y][i])
            x = f[x][i] , y = f[y][i];
    return f[x][0];
}
void getdif(int x , int fx)
{
    for(int i = head[x] ; i ; i = e[i].next)
        if(e[i].to != fx)
            getdif(e[i].to , x) , c[x] += c[e[i].to];
}
int main()
{
    scanf("%d",&n);
    int x , y , d;
    for(int i = 1 ; i <= n - 1 ; ++i)
        scanf("%d%d",&x,&y) , add(x,y) , add(y,x) , ed[++tot].from = x , ed[tot].to = y;
    dfs(1,1);
    OPTI();
    scanf("%d",&q);
    for(int i = 1 ; i <= q ; ++i)
    {
        scanf("%d%d",&x,&y);
        ++c[x] , ++c[y] , c[LCA(x,y)] -= 2;
    }
    getdif(1,0);
    for(int i = 1 ; i <= n-1 ; ++i)
    {
        int u = ed[i].from , v = ed[i].to;
        printf("%d ",dep[u] > dep[v] ? c[u] : c[v]);
    }
}