[COCI2016-2017 Contest#5 T6] Strelice 题解

标签：问题转化，树，动态规划，思维。

从第一列的每个点出发，其路径是固定的。枚举哪个点进行 dfs 难以实现，但如果将最后一列视为一个点，从终点出发，那么能够到达的第一列中的点即为叶子结点，路径形成了一棵树。这种转化的方法也巧妙地避开了死循环。

看一下这棵树，$7$ 是终点，由于终点列没法点亮，我们最少需要点亮 2 个点，即 $5$ 和 $6$。由于需要点亮恰好 $k$ 个点，我们需要在每个叶子结点到 $1$ 的路径上只有一个点被点亮的前提下，尽可能地多点亮几个点。那么对于每个叶子结点，从上到下依次编号为 $1\sim leaves$。我们先 dfs 一遍求出每个点包含的叶子结点编号最小值 $L$ 和最大值 $R$，上图中 $5$ 结点包含的范围就是 $1\sim 3$，$6$ 结点包含的就是 $4$，$7$ 结点包含的范围就是 $1\sim 4$。我们将所有树上的非叶子结点按照 $L$ 从小到大排序，然后用 $f(i,j)$ 记录当 $1\sim i$ 到根的路径上都有 1 个点被点亮时且一共点亮了 $j$ 盏时，第 $j$ 盏时什么，即记录路径。如果有一个点，覆盖区间为 $[L,R]$，那么 $f(R,j)$ 就应该从 $f(L-1,j-1)$ 转移来，从而满足不重不漏的效果。

对于不在树上的所有点，都是拿来凑数的，即当 $1\sim leaves$ 到根节点的路径上都只有一盏灯被点亮，但最多点亮的灯数 $tot$ 仍小于 $k$，那么还需补上 $tot-k$ 盏。若补不上，为 -1。当 $tot\ge k$，但不存在点亮 $k$ 盏能全部覆盖的方案，也为 -1。

具体代码实现

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
 
const int M=1e5+5,N=1e7+5;

inline int read()
{
	int x=0;static char ch;
	while(ch=getchar(),ch<48);
	do x=(x<<1)+(x<<3)+(ch^48);
	while(ch=getchar(),ch>=48);
	return x;
}
 
int n,P[M],fa[M],to[N];
bool one;
 
struct edge
{
    int u,v,nxt;
}E[N*5];
int hd[N],e_cnt;
void add(int x,int y,int z)
{
    E[++e_cnt]=(edge){x,y,hd[z]};
    hd[z]=e_cnt;
}
 
int find(int x)
{
    if(fa[x]!=x)fa[x]=find(fa[x]);
    return fa[x];
}
 
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
    	P[i]=read();
    	if(P[i]==1)one=true;
	}
	if(one)return printf("0"),0;
	
    sort(P+1,P+n+1);
    n=unique(P+1,P+n+1)-P-1;
     
    for(int i=1;i<=n;i++)fa[i]=i,to[P[i]]=i;
    for(int i=P[n]-1;i>=0;i--)
    	to[i]=to[i]?to[i]:to[i+1];
    for(int i=1;i<n;i++)
    {
        if(P[i+1]<2*P[i])add(i,i+1,P[i+1]%P[i]);
        for(int j=P[i]<<1;j<=P[n];j+=P[i])
        	if(to[j]&&P[to[j]]<j+P[i])
				add(i,to[j],P[to[j]]%P[i]);
    }
    long long ans=0;int ad_cnt=0;
    for(int x=0,u,v;x<=P[n];x++)
        for(int i=hd[x];i;i=E[i].nxt)
        {
            u=find(E[i].u),v=find(E[i].v);
            if(u!=v)fa[u]=v,ans+=x,ad_cnt++;
            if(ad_cnt==n-1)
				return printf("%lld",ans),0;
        }
    return 0;
}