记录详情

Accepted


  
# 状态 耗时 内存占用
#1 Accepted 2ms 400.0 KiB
#2 Accepted 2ms 488.0 KiB
#3 Accepted 3ms 828.0 KiB
#4 Accepted 8ms 984.0 KiB
#5 Accepted 3ms 1.574 MiB
#6 Accepted 4ms 2.723 MiB
#7 Accepted 5ms 3.094 MiB
#8 Accepted 5ms 3.891 MiB
#9 Accepted 6ms 4.27 MiB
#10 Accepted 7ms 4.859 MiB

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
    int num=0,bj=1;
    char x=getchar();
    while(x<'0'||x>'9') {
        if(x=='-')bj=-1;
        x=getchar();
    }
    while(x>='0'&&x<='9') {
        num=num*10+x-'0';
        x=getchar();
    }
    return num*bj;
}
struct Point {
    double x,y;
} a[105],b[105];
double Dist(Point a,Point b) {
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int m,n,k,Reach[105][105],f[105][105][105],Max[105][105],score[105],ans=0x7fffffff/2;
int map[105][105],vst[105],To[105],From[105];
bool Hungry_Dfs(int Now) { //寻找增广路 
    for(int i=1; i<=n; i++)
        if(map[Now][i]&&!vst[i]) {
            vst[i]=1;
            if(!To[i]||(Hungry_Dfs(To[i]))) {
                From[Now]=i;
                To[i]=Now;
                return true;
            }
        }
    return false;
}
void Dfs(int sum,int Now) { //已经用了sum个炸弹,炸到了Now(同时sum也表示炸掉了几段) 
    if(Now>m) {
        ans=min(ans,sum);
        return;
    }
    if(sum+score[Now]>=ans)return; //最优性剪枝(已经用的+乐观估价>=已有答案)
    memset(vst,0,sizeof(vst));
    queue<int>Q;
    int Maxl=Now-1; //下一个段最大结束位置 
    for(int i=1; i<=n; i++) {
        if(!To[i]) { //将所有没有匹配的炸弹入队 
            vst[i]=1;
            Q.push(i);
        }
    }
    while(!Q.empty()) {
        int Front=Q.front();
        Q.pop();
        Maxl=max(Maxl,Max[Front][Now]);
        for(int i=1; i<=sum; i++)
            if(map[i][Front]&&!vst[From[i]]) { //如果当前的炸弹可以被交换,那么当前的入队 
                vst[From[i]]=1;
                Q.push(From[i]);
            }
    }
    if(Maxl==Now-1)return;
    int From1[105],To1[105];
    memcpy(From1,From,sizeof(From));
    memcpy(To1,To,sizeof(To));
    memset(vst,0,sizeof(vst));
    for(int i=1; i<=n; i++)map[sum+1][i]=f[i][Now][Maxl]; //统计有的边
    Hungry_Dfs(sum+1); //扩展交错路 
    for(int i=Maxl; i>=Now; i--) { //枚举结束位置 
        for(int j=1; j<=n; j++)map[sum+1][j]=f[j][Now][i]; //统计有的边
        Dfs(sum+1,i+1); //继续搜索 
    }
    memcpy(From,From1,sizeof(From1));
    memcpy(To,To1,sizeof(To1));
}
int main() {
    m=Get_Int();
    n=Get_Int();
    k=Get_Int();
    for(int i=1; i<=m; i++) {
        a[i].x=Get_Int();
        a[i].y=Get_Int();
    } 
    for(int i=1; i<=n; i++) {
        b[i].x=Get_Int();
        b[i].y=Get_Int();
    }
    for(int i=1; i<=n; i++) //计算reach[i,j]:第i个炸弹能否炸到j武器 
        for(int j=1; j<=m; j++)
            Reach[i][j]=Dist(b[i],a[j])<=(k*k);
    for(int k=1; k<=n; k++) //计算f[i,j,k]:第i个炸弹能否炸到j~k这一段 
        for(int i=1; i<=m; i++) {
            f[k][i][i]=Reach[k][i];
            Max[k][i]=i-1;
            if(f[k][i][i])Max[k][i]=i;
            for(int j=i+1; j<=m; j++) {
                f[k][i][j]=f[k][i][j-1]&&Reach[k][j];
                if(f[k][i][j])Max[k][i]=j; //计算Max[i,j]:第i个炸弹从j开始炸所能达到的最大编号 
            }
        }
    for(int i=m; i>=1; i--) { //计算score[i]:如果可以重复使用炸弹,炸完i~m所需炸弹数(乐观估价) 
        int j=i-1;
        for(int k=1; k<=n; k++)j=max(Max[k][i],j);
        score[i]=score[j+1]+1;
    }
    Dfs(0,1);
    printf("%d\n",ans);
    return 0;
}

信息

递交者
类型
递交
题目
P1011 智破连环阵
语言
C++
递交时间
2021-12-30 16:12:29
评测时间
2021-12-30 16:13:10
评测机
分数
100
总耗时
48ms
峰值内存
4.859 MiB