解题报告 P3574 [POI2014]FAR-FarmCraft

题目内容

P3574

大意:村庄是一棵树,住在 1 号的管理要给每个房子送电脑,通过每个房子之间的道路需要 1 分钟,每个村民需要不同的时间安装电脑,而当管理把电脑送到村民后,村民会立即开始安装,最后管理会回到自己家给自己装电脑,求从管理出发到最后一个人装好电脑花费的时间。

解题思路

可以考虑每一个子树需要安装的最短时间。设住在 i 处的村民需要 c_i 的时间安装电脑, f_i 表示以 i 为根的子树全部安装好需要的最短时间,g_i 表示开车遍历以 i 为根的子树需要的最短时间,则有如下的方程:

f_i=\max(c_i,f_j+g_i+1)\
g_i\leftarrow g_i+g_j+2

其中 ji 的子节点,且 g_i 是动态更新的,就是遍历 j 之前的所有子树需要花的总时间。意思就是,对于一个 i 为根的子树,显然,第一次到 i 点的时候就让这里的村民开始装电脑得到的肯定更优,用这个时间与后面遍历下面节点的时间相比,总花费的时间是两者中间取最大的。而 f_j+g_i+1 的意义为,遍历过 j 节点之前的所有子节点需要的时间和 g_i 加上 j 节点需要的最短时间 f_j,至于 +1 就是从 i 节点走到 j 节点的花费。

而至于为什么是 +1 而不是 +2,是因为 \forall i:f_i-g_i\ge1,即等待的时间必然大于等于 1,所以只需要考虑从 i 进入 j 的时间,即为 1,而返回来的 1 的时间是被 f_j 覆盖掉的

不难发现,遍历的顺序会影响最终的结果,所以考虑贪心:可以发现,f_i-g_i 这段时间就是拿来等待的,做过接水问题的都知道要先处理等待时间大的,于是在转移前将子节点按照 f_i-g_i 排序即可。

#include <cstdio>
#include <cctype>
#include <vector>
#include <algorithm>

using namespace std;

const int maxn=500010;
int n,c[maxn],f[maxn],g[maxn],tmp[maxn];
vector<int> G[maxn];

inline void ins(int a,int b)
{
    G[a].push_back(b);
    G[b].push_back(a);
    return;
}

inline bool cmp(int x,int y)
{
    return f[x]-g[x] > f[y]-g[y];
}

inline int read()
{
    char c = getchar();
    int s = 0, x = 0;
    while (!isdigit(c))
    {
        if(c == '-')
            x = 1;
        c = getchar();
    }
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return x ? -s : s;
}

void dfs(int now,int fa)
{
    if(now!=1)//管理员的电脑最后装
        f[now]=c[now];
    int cnt=0;
    for(auto i:G[now])
        if(i!=fa)
            dfs(i,now);
    //一定要先遍历后记录儿子节点,不然会被下面的节点覆盖掉
    for(auto i:G[now])
        if(i!=fa)
            tmp[++cnt]=i;
    sort(tmp+1,tmp+cnt+1,cmp);
    for(int i=1;i<=cnt;i++)
        f[now]=max(f[now],f[tmp[i]]+g[now]+1),
        g[now]+=g[tmp[i]]+2;
}

int main()
{
    n=read();
    for(int i=1;i<=n;i++)
        c[i]=read();
    int a,b;
    for(int i=1;i<n;i++)
    {
        a=read(),b=read();
        ins(a,b);
    }
    dfs(1,0);
    printf("%d\n",max(c[1]+g[1],f[1]));//在最后也要注意
    return 0;
}

解题报告 P6082 [JSOI2015]salesman

题目内容

P6082

大意:给定一棵 n 个点的树,有点权,从 1 号点开始一次旅行,最后回到 1 号点。每到达一个点,就能获得等于该点点权的收益。每个点都有进入该点的次数限制,且每个点的收益只获得一次。求最大收益以及方案是否唯一。

解题思路

不难发现,这道题满足最优子结构,一棵子树的答案可由这棵子树的子树合并而来。

注意到进入限制这个性质,到达这个点进入了一次,去到每一棵子树再回来又是进入这个点一次,所以实际上我们只能访问这个点的 限制次数减一 棵子树。

而为了保证最优,需要使用贪心思想,当将一个节点的所有子树的信息处理完之后,将其从大到小排序,取前面的限制次数减一个并加起来(当然如果加到负数就肯定不加了)。

至于解的唯一性,注意到如果一个子树下的某个子树的解不唯一,那么这个子树的解肯定也不唯一。以及如果对于他的一棵子树,这个子树的答案为 0,则走与不走这个子树的效果是相同的,答案就会不唯一。还有,如果最后一个选的子树 a 的答案与下一个待选子树 b 的答案相同,说明可以选 a 也可以选 b,效果都是一样的,也会产生多解。

代码如下:

#include <utility>
#include <cstdio>
#include <cctype>
#include <queue>

using std::priority_queue;
using std::make_pair;
using std::vector;
using std::pair;

const int maxn=1e5+5;
int n,money[maxn],stop[maxn];
int f[maxn][2];

vector<int> g[maxn];

inline void ins(int from,int to)
{
    g[from].push_back(to);
    g[to].push_back(from);
    return;
}

inline int read()
{
    char c = getchar();
    int s = 0, x = 0;
    while (!isdigit(c))
    {
        if(c == '-')
            x = 1;
        c = getchar();
    }
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return x ? -s : s;
}

void dfs(int now,int fa)
{
    if(g[now].size()==1)//这是判断是否为叶子节点的
    {
        f[now][0]=money[now];
        return;
    }
    priority_queue<pair<int,int> > q;//排序用
    for(int i=0;i<g[now].size();i++)//访问下面的节点
    {
        if(g[now][i]!=fa)
        {
            dfs(g[now][i],now);//继续递归
            q.push(make_pair(f[g[now][i]][0],g[now][i]));//并且加入队列
        }
    }
    int lastChosen;
    for(int i=1; (!q.empty()) && (now==1 ? 1 : i<stop[now]);i++)
    {
        int to=q.top().second,val=q.top().first;
        if(val<0)//如果现在这棵子树已经小于 0 了,说明会产生负贡献,直接舍弃
            break;
        if(val==0)//有多解
            f[now][1]=1;
        f[now][0] += val;
        lastChosen=val;
        f[now][1] |= f[to][1];//下面的答案有多解的话也会产生多解
        q.pop();
    }
    f[now][0]+=money[now];
    if(q.size() && q.top().first==lastChosen)//如果下一个备选答案与上一个的相同,则有多解
        f[now][1]=1;
    return;
}

int main()
{
    n=read();
    for(int i=1;i<n;i++)
        money[i+1]=read();
    for(int i=1;i<n;i++)
        stop[i+1]=read();
    int from,to;
    for(int i=1;i<n;i++)
    {
        from=read(),to=read();
        ins(from,to);
    }
    dfs(1,0);
    printf("%d\n",f[1][0]);
    if(f[1][1])
        printf("solution is not unique\n");
    else
        printf("solution is unique\n");
    return 0;
}

解题报告 P1233 木棍加工

题目内容

P1233

一堆木头棍子共有 n 根,每根棍子的长度和宽度都是已知的。棍子可以被一台机器一个接一个地加工。机器处理一根棍子之前需要准备时间。准备时间是这样定义的:

第一根棍子的准备时间为 1 分钟;

如果刚处理完长度为 L,宽度为 W 的棍子,那么如果下一个棍子长度为 L_i,宽度为 W_i,并且满足 L\ge L_iW\ge W_i,这个棍子就不需要准备时间,否则需要 1 分钟的准备时间;

计算处理完 n 根棍子所需要的最短准备时间。比如,你有 5 根棍子,长度和宽度分别为 (4, 9),(5, 2),(2, 1),(3, 5),(1, 4),最短准备时间为 2(按 (4, 9)、(3, 5)、(1, 4)、(5, 2)、(2, 1) 的次序进行加工)。

解题思路

可以先贪心,后 dp,将所有的木棍先按照长度从大到小排序,如果长度相同就排宽度,然后就可以参考导弹拦截:由 Dilworth 定理,最大不上升子序列的个数为最大上升子序列的长度,因此我们只需要找到宽度的最长上升子序列就可以了。

代码:

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

struct stick
{
    int l,w;
}a[5005];

int f[5005];

inline bool cmp(stick a,stick b)
{
    return a.l==b.l?a.w>b.w:a.l>b.l;
}

int n;

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d %d",&a[i].l,&a[i].w);
    sort(a+1,a+n+1,cmp);
    int len=1;
    f[1]=a[1].w;
    for(int i=2;i<=n;i++)
    {
        if(a[i].w>f[len])
            f[++len]=a[i].w;
        else
        {
            int p=lower_bound(f+1,f+len+1,a[i].w)-f;
            f[p]=a[i].w;
        }
    }
    printf("%d\n",len);
    return 0;
}

解题报告 P1020 导弹拦截【NOIP1999TG】

题目内容

P1020

大意:求最长不下降子序列和最长上升子序列。

解题思路

半年前的坑,今天给填上。不难想出 O(n^2) 的做法:设 f_i 为以 a_i 结尾的 LIS 的长度,则有状态转移方程

f_i= \max_{j

每次都往前面扫描一遍,复杂度 O(n^2)

#include <cstdio>
#include <cstring>
#define maxn 100009
int a[maxn],b[maxn],h[maxn];

using namespace std;
int main()
{
    int ans1=0;
    memset(a,0,sizeof(a));
    memset(b,1,sizeof(b));
    memset(h,0x7ffffff,sizeof(h));
    int n=1,m=0;//n:the num of missiles, m:the num of sys
    while(scanf("%d",&a[n])!=EOF)
    {
        int l=0;
        for(int i=n-1;i>0;i--)
        {
            if(a[i]>=a[n]&&b[i]>l)
                l=b[i];
        }
        b[n]=l+1;
        if(b[n]>ans1) ans1=b[n];
        int x=0;
        for(int k=1;k<=n;k++)
        {
            if(h[k]>=a[n])
                if(x==0)
                    x=k;
                else if(h[k]<h[x])
                    x=k;
        }
        if(x==0)
        {
            m++;
            x=m;
        }
        h[x]=a[n];
        n++;
    }
    printf("%d %d\n",ans1,m);
    return 0;
}

当然这个算法太慢了,过不了洛谷的后面 10 个极限数据,因此我们需要 O(n\log n) 的做法,这个算法结合了二分查找和贪心。

如果我们此时设 f_i 表示长度为 i 的 LIS 的结尾的数字的话,思考:是不是当 f_i 越小,才越方便后面的数接进这个 LIS 呢,具体维护 f_i 的方法如下:

a_2 开始枚举每一个 a_i,如果新的 a_i 能接上这个已知最长的 LIS,那就接上去,否则就在 f 数组里面寻找能让 a_i 接上的 LIS 的长度,由于 f 数组一定满足单调递减,所以只需要利用二分查找在里面寻找第一个 f_j 使得 f_j\ge a_i 就可以了,然后更新对应的 f_j 即可。二分查找可以使用 STL 来偷懒降低代码复杂度。

该算法的复杂度为 O(n\log n)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn=100000+5;
int f1[maxn],f2[maxn],a[maxn],tot;

bool cmp(const int& a,const int& b)
{
    return a>b;
}

int main()
{
    memset(f1,0x7fffffff,sizeof(f1));
    memset(f2,0x7fffffff,sizeof(f2));
    while(scanf("%d",&a[++tot])!=EOF);
    f1[1]=a[1],f2[1]=a[1];
    //f[i]存储长度为i的序列的尾元素
    int len1=1,len2=1;//len表示查询到的LIS的最长长度
    for(int i=2;i<tot;i++)
    {
        if(a[i]<=f1[len1])//如果当前的a[i]可以接在最长的LIS的末尾
            f1[++len1]=a[i];//就接上去
        else
        {
            int p1=upper_bound(f1+1,f1+1+len1,a[i],cmp) - f1;
            //否则找到第一个大于他的
            f1[p1]=a[i];//然后接在后面,更新最小值
        }
        if(a[i]>f2[len2])
            f2[++len2]=a[i];
        else
        {
            int p2=lower_bound(f2+1,f2+len2+1,a[i])-f2;
            f2[p2]=a[i];
        }
    }
    printf("%d\n%d\n",len1,len2);
    return 0;
}