跳到主要内容

COCI2017/2018部分题目题解3

修改
· 阅读需 12 分钟
laieahoy
laieahoy
管理员

B. Cover​

每个矩形都是中心对称的，所以对于任意一个点，覆盖它与覆盖它第一象限对应点是等价的，第一象限对应点的意思是将这个点的横纵坐标都取绝对值后对应的点，那么我们就可以将不同位置的点统一移到第一象限，再对横坐标排序，这样就方便处理多了，后续说的点都是它在第一象限的对应点。

对于一个点 aa，如果存在一个点 bb 的横纵坐标都大于等于它的横纵坐标的话，因为一定会有一个矩形覆盖 bb，而覆盖 bb 的矩形一定会覆盖 aa，所以没有必要专门处理 aa，我们称 aa 这样的点为“被支配的点”，解题时可以直接忽略，剩下的点称为“有效点”。

现在，又因为我们的横坐标是从小到大排序的，所以某个点后面遍历到的点横坐标一定更大，因为“被支配的点”已经被筛掉了，所以这个点的纵坐标一定会比后面的点的纵坐标大，那么我们就能知道我们需要处理的点在横坐标排序的情况下，纵坐标是递减的，我们也可以这样来得到最终要处理的序列。

然后，我们的直觉告诉我们，需要从左往右依次处理，可以试一下，于是我们会发现，某个点要么以自己为端点新建一个矩形来包含自己，要么是通过之前的某个矩形扩展来包含自己，这就揭示来一个很重要的性质，无后效性，这就有很强的提示性了，我们自然会想到 DP。

状态设计方面，先设 dp[i]dp[i] 表示处理到第 ii 个有效点，且以第 ii 个点时，需要的最小面积，状态转移根据之前提到的某点的两种被覆盖情况，能写出方程为：

dp[i]=min1≤j≤idp[j−1]+x[i]∗y[j]dp[i]=min_{1\le j\le i}dp[j-1]+x[i]*y[j]

这里把之前提到的两种情况合并了一下，意思是保持到右边界为 j−1j-1 的情况不变，把后面的所有点用最小的面积来覆盖。

当然要注意代码中都是只算矩形在第一象限的部分的面积，所以最后答案要乘 44。

其实还可以用斜率优化的，但数据很小没必要（其实是不想写了）。

点击展开代码

代码：

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;

const int N=5005;
const ll inf=1e18;
int n;
struct node{
    ll x,y;
}a[N];
ll x[N],y[N],cnt,ma;
ll dp[N];

bool cmp(node a,node b)
{
    return a.x<b.x;
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y;
        a[i].x=abs(a[i].x),a[i].y=abs(a[i].y);
    }
    sort(a+1,a+1+n,cmp);
    for(int i=n;i;i--){
        if(a[i].y<ma) continue;
        x[++cnt]=a[i].x;
        y[cnt]=a[i].y;
        ma=max(ma,a[i].y);
    }
    reverse(x+1,x+1+cnt);
    reverse(y+1,y+1+cnt);
    for(int i=1;i<=cnt;i++) dp[i]=inf;
    dp[0]=0;
    for(int i=1;i<=cnt;i++){
        for(int j=1;j<=i;j++){
            dp[i]=min(dp[i],dp[j-1]+x[i]*y[j]);
        }
    }
    cout<<dp[cnt]*4<<"\n";

    return 0;
}

C. Go​

其实思路还是挺自然的，由于我们知道，已经到过的点再到一次是不会产生贡献的，又知道，每次只会移动一个点的距离，那么很明显的一点是，如果把我们已经走过的地方看作一段连续的区间，那么能产生新贡献的情况就是在这个站在了区间的端点上，向左右某个端点再扩展到有贡献的地方。那么就能想到，设 dp[l][r][t][0/1]dp[l][r][t][0/1] 表示当前已走过的地方形成的连续区间是 ll 到 rr，已用了 tt 的时间，现在在左端点/右端点时的最大的糖果价值。但是这个状态设计的空间是会爆的，但我们发现，我们在设计状态的时候，其实只是关心会对答案产生贡献的地方，这样的点才会成为有意义的左右端点，那么我们会预设很多不会在 dp 中用到的点，而可能产生贡献的地方是精灵所在处，所以我们稍微调整一下状态定义：设 dp[l][r][t][0/1]dp[l][r][t][0/1] 表示当前已走过的地方形成的连续区间是 a[l]a[l] 到 a[r]a[r]，已用了 tt 的时间，现在在左端点/右端点时的最大的糖果价值，其中，a[l]a[l] 与 a[r]a[r] 是题目中给出的第 ll 个精灵所在的位置与第 rr 个精灵所在的位置。

状态转移也比较套路（T[i]T[i] 和 b[i]b[i] 分别是题目给出的精灵捕获时间限制与精灵能给的糖果价值）：

dp[l][r][t][0]=max(dp[l+1][r][t−(T[l+1]−T[l])][0],dp[l+1][r][t−(T[r]−T[l])][1])+b[l]∗[T[i]>t]dp[l][r][t][1]=max(dp[l][r−1][t−(T[r]−T[r−1])][1],dp[l][r−1][t−(T[r]−T[l])][0])+b[l]∗[T[i]>t]dp[l][r][t][0]=max(dp[l+1][r][t-(T[l+1]-T[l])][0],dp[l+1][r][t-(T[r]-T[l])][1])+b[l]*[T[i]>t]\\ dp[l][r][t][1]=max(dp[l][r-1][t-(T[r]-T[r-1])][1],dp[l][r-1][t-(T[r]-T[l])][0])+b[l]*[T[i]>t]\\

注意转移中时间是否够的判断条件是 [T[i]>t][T[i]>t]，而不是 [T[i]≥t][T[i]\ge t]，这是因为题目中给了第 11 秒在 kk 位置，而不是在第 00 秒在 kk 位置，但是默认 dp 中 tt 是从 00 开始的，所以其实判断条件是 [T[i]≥t+1][T[i]\ge t+1]，所以写成了 [T[i]>t][T[i]>t]。

现在 dp 的主要框架搭出来了，需要考虑的是一些细节问题，比如初始化。

初始化时，我们会找到与 kk 相同的 a[i]a[i] 记为 startstart，这样我们会初始化 dp[start][start][0][0/1]dp[start][start][0][0/1] 为 b[start]b[start]，其他的为 −inf-inf，但如果找不到呢，我们可以考虑一个策略，就是自己加一个本来不存在的精灵点，使它的位置为 kk，这样就能正常初始化与转移了，不过需要注意，原本的 a[i]a[i] 是题目本来给的就是升序的，加点后是需要重新排序的。

点击展开代码

代码：

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;

const int N=105,M=2005;
int n,k,m,ma,start,ans;
struct node{
    int a,b,t;
}w[N];
int dp[N][N][M][2];

bool cmp(node a,node b)
{
    return a.a<b.a;
}

int main()
{
    cin>>n>>k>>m;
    for(int i=1;i<=m;i++) cin>>w[i].a>>w[i].b>>w[i].t,ma=max(ma,w[i].t);
    w[++m]={k,0,0};
    sort(w+1,w+1+m,cmp);
    for(int i=1;i<=m;i++){
        if(w[i].a==k){
            start=i;
            break;
        }
    }
    memset(dp,-0x3f,sizeof dp);
    dp[start][start][0][0]=dp[start][start][0][1]=0;
    for(int t=0;t<=ma;t++){
        for(int len=1;len<=m;len++){
            for(int l=1;l+len-1<=m;l++){
                int r=l+len-1;
                if(l>start||r<start||l>r) continue;
                int t1=t-w[l+1].a+w[l].a;
                if(t1>=0){
                    dp[l][r][t][0]=max(dp[l][r][t][0],
                    dp[l+1][r][t1][0]+w[l].b*(w[l].t>t));
                }
                int t2=t-w[r].a+w[l].a;
                if(t2>=0){
                    dp[l][r][t][0]=max(dp[l][r][t][0],
                    dp[l+1][r][t2][1]+w[l].b*(w[l].t>t));
                }
                int t3=t-w[r].a+w[r-1].a;
                if(t3>=0){
                    dp[l][r][t][1]=max(dp[l][r][t][1],
                    dp[l][r-1][t3][1]+w[r].b*(w[r].t>t));
                }
                int t4=t-w[r].a+w[l].a;
                if(t4>=0){
                    dp[l][r][t][1]=max(dp[l][r][t][1],
                    dp[l][r-1][t4][0]+w[r].b*(w[r].t>t));
                }
                ans=max(ans,max(dp[l][r][t][1],dp[l][r][t][0]));
            }
        }
    }
    cout<<ans<<"\n";

    return 0;
}

D. Dostavljač​

看题面基本可以确定是树形背包问题，所以可以先试着设计 DP。

我们知道，因为只有一个人，所以他若先访问某个节点的某棵子树，那么他想继续去访问该点的其他子树时，必须要先回到这个点，再向下走，于是我们可以设计出一个能够转移的状态 dp[u][i][0/1]dp[u][i][0/1] 表示现在正在遍历 uu 这个点的子树，已经用了 ii 的时间，现在是否回到了 uu 点，但是我们发现，这样正常遍历时还是不好转移，因为加上这个点某儿子的贡献时，要依赖于点 uu 是否回到了自己，那么最后得到的没有回来的可能一定是只有最后一个被遍历到的儿子没有会 uu 的情况，这样就漏情况了。

但是，我们想到，既然出问题的只是不回到 uu 的情况，而且漏情况的原因是我们只有最后一个能够不回来，那么其实我们可以改变一下状态的定义：设 dp[u][i][1]dp[u][i][1] 为没有回到 uu 点，且没有回到 uu 点的这棵子树是最后遍历的子树，dp[u][i][0]dp[u][i][0] 的定义不变。那么我们利用了只有最后遍历的子树能够不回来的性质，先在状态中钦定这样的子树是最后遍历的，这样就使得每个儿子都可以作为那个不回到父亲的点，这样状态设计就不会漏了，而且我们发现，后续的转移也轻松了。

设 vv 为 uu 当前遍历到的儿子，状态转移的式子就是：

dp[u][i+j+2][0]=dp[u][i][0]+dp[v][j][0]dp[u][i+j+2][1]=dp[u][i][1]+dp[v][j][0]dp[u][i+j+1][1]=dp[u][i][0]+dp[v][j][1]dp[u][i+j+2][0]=dp[u][i][0]+dp[v][j][0]\\ dp[u][i+j+2][1]=dp[u][i][1]+dp[v][j][0]\\ dp[u][i+j+1][1]=dp[u][i][0]+dp[v][j][1]\\

之所以有 +1+1 与 +2+2 的地方，是因为处理子树时，没有处理到过 u,vu,v 之间的边，所以如果有从 uu 到 vv 再到 uu 的过程，就需要额外加 22 的时间消耗，而只有 uu 到 vv 时，只用加 11 的时间消耗。

其他的实现就用经典的树形背包的写法实现即可，具体看代码。

点击展开代码

代码：

#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;

const int N=505,inf=1e9;
int n,m;
int a[N];
int f[N][N][2],h[N][2],lim[N];
vector<int> g[N];

void dfs(int u,int fa)
{
    lim[u]=min(m,1);
    for(int i=0;i<=m;i++) f[u][i][0]=f[u][i][1]=-inf;
    f[u][0][0]=f[u][0][1]=0;
    f[u][1][0]=f[u][1][1]=a[u];
    for(int v:g[u]){
        if(v==fa) continue;
        dfs(v,u);
        for(int i=0;i<=m;i++) h[i][0]=h[i][1]=-inf;
        for(int i=0;i<=lim[u];i++){
            h[i][0]=max(h[i][0],f[u][i][0]);
            h[i][1]=max(h[i][1],f[u][i][1]);
            for(int j=0;j<=lim[v];j++){
                if(i+j+2<=m){
                    if(f[u][i][0]>-inf&&f[v][j][0]>-inf){
                        h[i+j+2][0]=max(h[i+j+2][0],
                        f[u][i][0]+f[v][j][0]);
                    }
                    if(f[u][i][1]>-inf&&f[v][j][0]>-inf){
                        h[i+j+2][1]=max(h[i+j+2][1],
                        f[u][i][1]+f[v][j][0]);
                    }
                }
                if(i+j+1<=m){
                    if(f[u][i][0]>-inf&&f[v][j][1]>-inf){
                        h[i+j+1][1]=max(h[i+j+1][1],
                        f[u][i][0]+f[v][j][1]);
                    }
                }
            }
        }
        for(int i=0;i<=m;i++){
            f[u][i][0]=h[i][0];
            f[u][i][1]=h[i][1];
        }
        lim[u]=min(m,lim[u]+lim[v]+2);
    }
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);
    cout<<max(f[1][m][0],f[1][m][1])<<"\n";

    return 0;
}