题目描述

给定一个长度为 n
的整数序列 a1,a2,…,an
。

请你选出一个该序列的严格上升子序列，要求所选子序列的各元素之和尽可能大。

请问这个最大值是多少？

输入格式
第一行包含整数 n
。

第二行包含 n
个整数 a1,a2,…,an
。

输出格式
输出最大的上升子序列和。

数据范围
对于前三个测试点，1≤n≤4
。
对于全部测试点， 1≤n≤105,1≤ai≤109
。

样例

输入样例1：
2
100 40
输出样例1：
100
输入样例2：
4
1 9 7 10
输出样例2：
20

算法1

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
const int N=100010;
int n,m;
int w[N],q[N];
LL f[N];//以a[i]结尾的最大上升子序列集合的最大值
LL tr[N];//树状数组
int lowbit(int x)
{
    return x&-x;
}
void add(int x,LL v)
{
    for(int i=x;i<=m;i+=lowbit(i))tr[i]=max(tr[i],v);//和求和性质一样
}
LL query(int x)
{
    LL res=0;
    for(int i=x;i>=1;i-=lowbit(i))
    res=max(res,tr[i]);//和求前缀和性质一样
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&w[i]);
    memcpy(q,w,sizeof w);
    sort(q,q+n);//数组排序
    m=unique(q,q+n)-q;//去重复元素完的大小
    LL res=0;
    for(int i=0;i<n;i++)
    {
        int x=lower_bound(q,q+m,w[i])-q+1;//数组元素映射成下标，下标从1开始
        f[i]=query(x-1)+w[i];//比x小的数加上当前数的和
        res=max(res,f[i]);
        add(x,f[i]);//加到树状数组里面
    }
    printf("%lld\n",res);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
const int N=100010;
int n,m;
int w[N],q[N];
LL f[N];//以a[i]结尾的最大上升子序列集合的最大值
LL tr[N];//树状数组
int lowbit(int x)
{
    return x&-x;
}
void add(int x,LL v)
{
    for(int i=x;i<=m;i+=lowbit(i))tr[i]=max(tr[i],v);//和求和性质一样
}
LL query(int x)
{
    LL res=0;
    for(int i=x;i>=1;i-=lowbit(i))
    res=max(res,tr[i]);//和求前缀和性质一样
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&w[i]);
    memcpy(q,w,sizeof w);
    sort(q,q+n);//数组排序
    m=unique(q,q+n)-q;//去重复元素完的大小
    LL res=0;
    for(int i=0;i<n;i++)
    {
        int x=lower_bound(q,q+m,w[i])-q+1;//数组元素映射成下标，下标从1开始
        f[i]=query(x-1)+w[i];//比x小的数加上当前数的和
        res=max(res,f[i]);
        add(x,f[i]);//加到树状数组里面
    }
    printf("%lld\n",res);
    return 0;
}

题目描述

n
个小朋友站成一排。

现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。

每个小朋友都有一个不高兴的程度。

开始的时候，所有小朋友的不高兴程度都是 0
。

如果某个小朋友第一次被要求交换，则他的不高兴程度增加 1
，如果第二次要求他交换，则他的不高兴程度增加 2
（即不高兴程度为 3
），依次类推。当要求某个小朋友第 k
次交换时，他的不高兴程度增加 k
。

请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。

如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。

输入格式
输入的第一行包含一个整数 n
，表示小朋友的个数。

第二行包含 n
个整数 H1,H2,…,Hn
，分别表示每个小朋友的身高。

输出格式
输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。

数据范围
1≤n≤100000
,
0≤Hi≤1000000

样例

输入样例：
3
3 2 1
输出样例：
9

算法1

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
const int N=1000010;
int n;
int h[N],tr[N];//树状数组
int sum[N];//每个数字不高兴度
int lowbit(int x)
{
    return x&-x;//返回2的k次方
}
void add(int x,int v)
{
    for(int i=x;i<N;i+=lowbit(i))tr[i]+=v;//不高兴度加到数组里
}
int query(int x)
{
    int res=0;
    for(int i=x;i>=1;i-=lowbit(i))res+=tr[i];//求前缀和
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&h[i]),h[i]++;//数组下标转换为1开头
    for(int i=0;i<n;i++)//每个数前面有多少数比它大
    {
        sum[i]=query(N-1)-query(h[i]);//求不高兴度之和
        add(h[i],1);//开始映射不高兴度，每一次相应的tr[i]都加1
    }
    memset(tr,0,sizeof tr);//清空数组
    for(int i=n-1;i>=0;i--)//每个数后面有多少数比他小
    {
        sum[i]+=query(h[i]-1);//不高兴度之和
        add(h[i],1);//开始映射不高兴度，每一次相应的tr[i]都加1
    }
    LL res=0;
    for(int i=0;i<n;i++)res+=(LL)sum[i]*(sum[i]+1)/2;//每个数字的不高兴度之和等差公式，再加上所有的
    cout<<res<<endl;
    return 0;
}

/*#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long  LL;
const int N=1000010;
int n;
int h[N],tr[N],sum[N];
int lowbit(int x)
{
    return x & -x;
}
void add(int x, int v)
{
    for (int i = x; i < N; i += lowbit(i)) tr[i] += v;
}int query(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &h[i]), h[i] ++ ;
// 求每个数前面有多少个数比它大
    for (int i = 0; i < n; i ++ )
    {
        sum[i] = query(N - 1) - query(h[i]);
        add(h[i], 1);
    }// 每个数后面有多少个数比它小
    memset(tr, 0, sizeof tr);
    for (int i = n - 1; i >= 0; i -- )
    {
        sum[i] += query(h[i] - 1);
        add(h[i], 1);
    } LL res = 0;
    for (int i = 0; i < n; i ++ ) res += (LL)sum[i] * (sum[i] + 1) / 2;
cout<<res<<endl;
return 0;
}*/
#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
const int N=1000010;
int n;
int h[N],tr[N];//树状数组
int sum[N];//每个数字不高兴度
int lowbit(int x)
{
    return x&-x;//返回2的k次方
}
void add(int x,int v)
{
    for(int i=x;i<N;i+=lowbit(i))tr[i]+=v;//不高兴度加到数组里
}
int query(int x)
{
    int res=0;
    for(int i=x;i>=1;i-=lowbit(i))res+=tr[i];//求前缀和
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&h[i]),h[i]++;//数组下标转换为1开头
    for(int i=0;i<n;i++)//每个数前面有多少数比它大
    {
        sum[i]=query(N-1)-query(h[i]);//求不高兴度之和
        add(h[i],1);//开始映射不高兴度，每一次相应的tr[i]都加1
    }
    memset(tr,0,sizeof tr);//清空数组
    for(int i=n-1;i>=0;i--)//每个数后面有多少数比他小
    {
        sum[i]+=query(h[i]-1);//不高兴度之和
        add(h[i],1);//开始映射不高兴度，每一次相应的tr[i]都加1
    }
    LL res=0;
    for(int i=0;i<n;i++)res+=(LL)sum[i]*(sum[i]+1)/2;//每个数字的不高兴度之和等差公式，再加上所有的
    cout<<res<<endl;
    return 0;
}

题目描述

在X森林里，上帝创建了生命之树。

他给每棵树的每个节点（叶子也称为一个节点）上，都标了一个整数，代表这个点的和谐值。

上帝要在这棵树内选出一个非空节点集 S
，使得对于 S
中的任意两个点 a,b
，都存在一个点列 {a,v1,v2,…,vk,b}
使得这个点列中的每个点都是 S
里面的元素，且序列中相邻两个点间有一条边相连。

在这个前提下，上帝要使得 S
中的点所对应的整数的和尽量大。

这个最大的和就是上帝给生命之树的评分。

经过 atm 的努力，他已经知道了上帝给每棵树上每个节点上的整数。

但是由于 atm 不擅长计算，他不知道怎样有效的求评分。

他需要你为他写一个程序来计算一棵树的分数。

输入格式
第一行一个整数 n
表示这棵树有 n
个节点。

第二行 n
个整数，依次表示每个节点的评分。

接下来 n−1
行，每行 2
个整数 u,v
，表示存在一条 u
到 v
的边。

由于这是一棵树，所以是不存在环的。

树的节点编号从 1
到 n
。

输出格式
输出一行一个数，表示上帝给这棵树的分数。

数据范围
1≤n≤105
,
每个节点的评分的绝对值均不超过 106
。

样例

输入样例：
5
1 -2 -3 4 5
4 2
3 1
1 2
2 5
输出样例：
8

算法1

参考文献

C++ 代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 100010, M = N * 2;

int n;
int w[N];//权值
int h[N], e[M], ne[M], idx;//邻接表存稀疏图
LL f[N];//以u为根的子树中包含u的连通块的权值的最大值

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;//头插法
}

void dfs(int u, int father)//不回溯
{
    f[u] = w[u];
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (j != father)//不是根节点
        {
            dfs(j, u);//遍历子节点
            f[u] += max(0ll, f[j]);
        }
    }
}

int main()
{
    scanf("%d", &n);
    memset(h, -1, sizeof h);//头节点初始化

    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);//无向边加两遍
    }

    dfs(1, -1);//深搜

    LL res = f[1];
    for (int i = 2; i <= n; i ++ ) res = max(res, f[i]);

    printf("%lld\n", res);

    return 0;
}

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 100010, M = N * 2;

int n;
int w[N];//权值
int h[N], e[M], ne[M], idx;//邻接表存稀疏图
LL f[N];//以u为根的子树中包含u的连通块的权值的最大值

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;//头插法
}

void dfs(int u, int father)//不回溯
{
    f[u] = w[u];
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (j != father)//不是根节点
        {
            dfs(j, u);//遍历子节点
            f[u] += max(0ll, f[j]);
        }
    }
}

int main()
{
    scanf("%d", &n);
    memset(h, -1, sizeof h);//头节点初始化

    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);//无向边加两遍
    }

    dfs(1, -1);//深搜

    LL res = f[1];
    for (int i = 2; i <= n; i ++ ) res = max(res, f[i]);

    printf("%lld\n", res);

    return 0;
}

题目描述

给一棵有 m
个节点的无根树，你可以选择一个度数大于 1
的节点作为根，然后给一些节点（根、内部节点、叶子均可）着以黑色或白色。

你的着色方案应保证根节点到各叶子节点的简单路径上都至少包含一个有色节点，哪怕是这个叶子本身。

对于每个叶子节点 u
，定义 cu
为从根节点到 u
的简单路径上最后一个有色节点的颜色。

给出每个 cu
的值，设计着色方案使得着色节点的个数尽量少。

输入格式
第一行包括两个数 m,n
，依次表示节点总数和叶子个数，节点编号依次为 1
至 m
，其中编号 1
至 n
是叶子。

接下来 n
行每行一个 0
或 1
的数，其中 0
表示黑色，1
表示白色，依次为 c1,c2,…,cn
的值。

接下来 m−1
行每行两个整数 a,b
，表示节点 a
与 b
有边相连。

输出格式
输出仅一个数，表示着色节点数的最小值。

数据范围
数据 1 2 3 4 5 6 7 8 9 10
M 10 50 100 200 400 1000 4000 8000 10000 10000
N 5 23 50 98 197 498 2044 4004 5021 4996

样例

输入样例：
5 3
0
1
0
1 4
2 5
4 5
3 5
输出样例：
2

算法1

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=10010,M=N*2,INF=1e8;
int m,n;
int h[N],c[N],e[M],ne[M],idx;//邻接表存稀疏图
int f[N][2];//染色0或1
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;//头插法
}
void dfs(int u,int fa)
{
    if(u<=n)return ;//如果是叶节点，return
    f[u][0]=f[u][1]=1;//无论染色0还是1都需要一次操作
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==fa)//如果是父节点，跳过
        continue;
        dfs(j,u);//dfs子节点
        f[u][0]+=min(f[j][0]-1,f[j][1]);//染色0的话少一次操作，染色1不少
        f[u][1]+=min(f[j][1]-1,f[j][0]);//染色1少一次操作，染色0不少
    }
}
int main()
{
    scanf("%d%d",&m,&n);
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&c[i]);
    }
    for(int i=1;i<=n;i++)
    {
        f[i][c[i]]=1;//染色是c[i]则需要一次操作
        f[i][!c[i]]=INF;//其他颜色不对
    }
    for(int i=0;i<m-1;i++)//边
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);//无向边加两次
    }
    dfs(n+1,-1);//第n+1个节点不是叶子节点
    printf("%d\n",min(f[n+1][0],f[n+1][1]));
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=10010,M=N*2,INF=1e8;
int m,n;
int h[N],c[N],e[M],ne[M],idx;//邻接表存稀疏图
int f[N][2];//染色0或1
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;//头插法
}
void dfs(int u,int fa)
{
    if(u<=n)return ;//如果是叶节点，return
    f[u][0]=f[u][1]=1;//无论染色0还是1都需要一次操作
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==fa)//如果是父节点，跳过
        continue;
        dfs(j,u);//dfs子节点
        f[u][0]+=min(f[j][0]-1,f[j][1]);//染色0的话少一次操作，染色1不少
        f[u][1]+=min(f[j][1]-1,f[j][0]);//染色1少一次操作，染色0不少
    }
}
int main()
{
    scanf("%d%d",&m,&n);
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&c[i]);
    }
    for(int i=1;i<=n;i++)
    {
        f[i][c[i]]=1;//染色是c[i]则需要一次操作
        f[i][!c[i]]=INF;//其他颜色不对
    }
    for(int i=0;i<m-1;i++)//边
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);//无向边加两次
    }
    dfs(n+1,-1);//第n+1个节点不是叶子节点
    printf("%d\n",min(f[n+1][0],f[n+1][1]));
    return 0;
}

题目描述

Ural 大学有 N
名职员，编号为 1∼N
。

他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。

每个职员有一个快乐指数，用整数 Hi
给出，其中 1≤i≤N
。

现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。

在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

输入格式
第一行一个整数 N
。

接下来 N
行，第 i
行表示 i
号职员的快乐指数 Hi
。

接下来 N−1
行，每行输入一对整数 L,K
，表示 K
是 L
的直接上司。

输出格式
输出最大的快乐指数。

数据范围
1≤N≤6000
,
−128≤Hi≤127

样例

输入样例：
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
输出样例：
5

算法1

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=6010;
int n;
int h[N],e[N],ne[N],idx;//邻接表存图
int happy[N];
int f[N][2];//
bool has_fa[N];//是否有父节点
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;//头插法存邻接表
}
void dfs(int u)//从根节点深搜
{
    f[u][1]=happy[u];//权值
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        dfs(j);
        f[u][1]+=f[j][0];//如果选中上司，则直接下属不选
        f[u][0]+=max(f[j][0],f[j][1]);//如果不选上司，则直接下属可以选也可以不选
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&happy[i]);
    }
    memset(h,-1,sizeof h);//头节点初始化
    for(int i=0;i<n-1;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);//b是a的直接上司
        add(b,a);
        has_fa[a]=true;//a有父节点
    }
    int root=1;
    while(has_fa[root])root++;//寻找没有父节点的节点作为根节点
    dfs(root);
    printf("%d\n",max(f[root][0],f[root][1]));//根节点选或不选
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=6010;
int n;
int h[N],e[N],ne[N],idx;//邻接表存图
int happy[N];
int f[N][2];//
bool has_fa[N];//是否有父节点
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;//头插法存邻接表
}
void dfs(int u)//从根节点深搜
{
    f[u][1]=happy[u];//权值
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        dfs(j);
        f[u][1]+=f[j][0];//如果选中上司，则直接下属不选
        f[u][0]+=max(f[j][0],f[j][1]);//如果不选上司，则直接下属可以选也可以不选
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&happy[i]);
    }
    memset(h,-1,sizeof h);//头节点初始化
    for(int i=0;i<n-1;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);//b是a的直接上司
        add(b,a);
        has_fa[a]=true;//a有父节点
    }
    int root=1;
    while(has_fa[root])root++;//寻找没有父节点的节点作为根节点
    dfs(root);
    printf("%d\n",max(f[root][0],f[root][1]));//根节点选或不选
    return 0;
}