P1526

Drot_Lee · 2021-08-15 22:11:56 · 题解

智破连环阵

这题是黑题但水的一批。

题目描述

给你 m 个武器的坐标、n 个炸弹的坐标，用炸弹炸范围半径为 k 内的武器，炸弹用完了就没了，可以改变炸弹顺序，求最少要多少炸弹才能将武器炸完。

题目链接

首先发现每一个炸弹能炸的武器一定是编号连续的。

这是因为只有前一个武器被摧毁，后一个才能被摧毁，并且一个炸弹能持续5分钟，这注定了每个炸弹一定能将能摧毁的都摧毁掉。

用 dfs 的话，可以将 1\backsim m 个武器分为若干小块，每个小块由各自一个的炸弹炸。

那么枚举在哪里分段。

那么先维护出来每一个炸弹能炸到的武器，用你初中学过的勾股即可。

然后就可以通过递推方式求出每一个炸弹能炸到的编号最大的武器（正着枚举炸弹，倒着枚举武器，显然第 i 个炸弹炸到第 j 个武器时，能够转移过来这个炸弹能炸到的最远的武器）。

已经递推出每个炸弹能炸的区间了。就可以愉快的 dfs 了。

当然要剪枝：

设一个数组 g。

用来计：在炸弹可以无限重复用的情况下，从第 i 个武器到最后一个武器最少用多少个炸弹，即预估的还要用的最少炸弹数。

这样的话，当我们 dfs 到一个新的状态时，只需要提前判断当前已用的炸弹加上预估的还要的最少的炸弹数是否小于已有的答案，若否，则直接返回即可。

我们发现有有许多炸弹对应一段区间的情况。

用一个二分图最大匹配即可解决。

于是流程就是：处理处每个炸弹能炸的武器、地推出每个炸弹最远能炸多远、从每个位置炸到最后最少用的炸弹数、 dfs 、二分图最大匹配。

于是你就可以水掉他了。

代码注释见：

#include<bits/stdc++.h>
using namespace std;
int read () 
{
    int x = 0 , f = 1 ; char ch = getchar () ; 
    while ( ! isdigit ( ch ) ) { if ( ch == '-' ) f = -1 ; ch = getchar () ; }
    while ( isdigit ( ch ) ) { x = ( x << 3 ) + ( x << 1 ) + ch - 48 ; ch = getchar () ; } 
    return x * f ; 
}

int m , n , k , ans , tmp [ 101 ] , f [ 101 ] [ 101 ] , g [ 101 ] , J [ 101 ] [ 101 ]  ; 
bool vis [ 101 ] , fl [ 101 ] [ 101 ] ;

struct node { 
    int x  , y ; 
} a [ 101 ] , b [ 101 ] ; 

int fang ( int x ) 
{
    return x * x ; 
}
bool found ( int x ) // 二分图最大匹配 
{
    for ( int i = 1 ; i <= n ; i ++ ) 
        if ( fl [ i ] [ x ] && vis [ i ] ) 
        {
            vis [ i ] = 0 ; 
            if ( tmp [ i ] == -1 || found ( tmp [ i ] ) ) 
            {
                tmp [ i ] = x ; 
                return 1 ; 
            }
        }
    return 0 ; 
}
void dfs ( int x , int y ) // 分到第 x 个武器，已经分了 y 个块 
{
     if ( y + g [ x ] >= ans ) return ; // 提前预知不优，返回 
     if ( x > m ) 
     {
        ans = y ; // 更新答案 
        return ; 
     }
     int tmpp [ 101 ] ; 
     for ( int i = x ; i <= m ; i ++ ) // 枚举从哪里分开 
     {
        for ( int j = 1 ; j <= n ; j ++ ) 
        {
            tmpp [ j ] = tmp [ j ] ; // 记录副本，方便还原现场 
            if ( J [ j ] [ x ] && f [ j ] [ x ] >= i ) 
            fl [ j ] [ y + 1 ] = 1 ; 
        }
        memset ( vis , 1 , sizeof ( vis ) ) ; 
        if ( found ( y + 1 ) ) dfs ( i + 1 , y + 1 ) ; // 继续递归 
        for ( int j = 1 ; j <= n ; j ++ ) // 还原现场 
        {
            tmp [ j ] = tmpp [ j ] ; 
            if ( J [ j ] [ x ] == 1 && f [ j ] [ x ] >= i ) 
                fl [ j ] [ y + 1 ] = 0 ; 
        }
    }
}

int main () 
{
    m = read () ; n = read () ; k = read () ; 
    for ( int i = 1 ; i <= m ; i ++ ) b [ i ] . x = read () , b [ i ] . y = read () ;
    for ( int i = 1 ; i <= n ; i ++ ) a [ i ] . x = read () , a [ i ] . y = read () ; 
    for ( int i = 1 ; i <= m ; i ++ ) 
        for ( int j = 1 ; j <= n ; j ++ ) 
            if ( fang ( a [ j ] . x - b [ i ] . x ) + fang ( a [ j ] . y - b [ i ] . y ) <= fang ( k ) ) J [ j ] [ i ] = 1 ; // 判断能否炸到 
    for ( int i = 1 ; i <= n ; i ++ ) 
        for ( int j = m ; j >= 1 ; j -- ) 
            if ( J [ i ] [ j ] ) f [ i ] [ j ] = max ( j , f [ i ] [ j + 1 ] ) ; //递推求最大能炸到的武器 
    memset ( g , 0x3f , sizeof ( g ) ) ; 
    g [ m + 1 ] = 0 ; 
    for ( int i = m ; i >= 1 ; i -- )
        for ( int j = 1 ; j <= n ; j ++ ) 
            if ( J [ j ] [ i ] ) g [ i ] = min ( g [ i ] , g [ f [ j ] [ i ] + 1 ] + 1 ) ; // 递推求从该点武器炸到最后武器最少用的炸弹 
    ans = n ; // 最差要用 n 个炸弹，因此初始化为 n  
    memset ( tmp , -1 , sizeof ( tmp ) ) ; 
    dfs ( 1 , 0 ) ;  // dfs 
    cout << ans << endl ; 
    return 0 ; 
}

后记

这是我第一次写题解，望通过 QwQ。