题解 - Vijos

-2

Kenny10001 LV 7 @ 2016-05-19 16:38:33

#include <cstdio>
#include <cstring>
#include <cstdlib>
#define l 110
int x1[l],y1[l],x2[l],y2[l],m,n,k,MAXT[l][l],ans=1000000000,a[l],b[l],vis[l],dl[l],head,tail,perfect[l];
bool reach[l][l],can[l][l][l],g[l][l];
void input_data()
{
scanf("%d%d%d",&m,&n,&k);
for (int i=1;i<=m;i++)
scanf("%d%d",&x1[i],&y1[i]);
for (int i=1;i<=n;i++)
scanf("%d%d",&x2[i],&y2[i]);
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++)
reach[i][j]=((x1[i]-x2[j])(x1[i]-x2[j])+(y1[i]-y2[j])(y1[i]-y2[j]))<=(k*k);//reach[i][j]表示i号武器能否被j号炸弹炸到。
}
void pre()
{
for (int i=1;i<=m;i++)
{
for (int j=1;j<=n;j++)
can[i][i][j]=reach[i][j];
for (int j=i+1;j<=m;j++)
for (int d=1;d<=n;d++)
can[i][j][d]=can[i][j-1][d] && reach[j][d];//更新
for (int j=1;j<=n;j++)
{
MAXT[i][j]=i-1;//MAXT[i][j]表示j号炸弹从i号武器开始能够炸到的最大编号
for (int d=i;d<=m;d++)
if (can[i][d][j]) MAXT[i][j]=d;//利用can数组来更新MAXT数组
}
}
perfect[m+1]=0;//perfect[i]表示i-m号武器最少需要多少个炸弹才能炸掉(可以重复使用炸弹);
for (int i=m;i>=1;i--)
{
int t=i-1;
for (int j=1;j<=n;j++)
if (MAXT[i][j]>t) t=MAXT[i][j];//找到这个炸弹的最大使用限度。
perfect[i]=perfect[t+1]+1;//从t+1转移到当前状态。
}
}
bool xiongyali(int x)//匈牙利算法
{
for (int i=1;i<=n;i++)
if (g[x][i] && !vis[i])
{
vis[i]=true;
if (b[i]==0 || xiongyali(b[i]))
{
a[x]=i;
b[i]=x;
return true;
}
}
return false;
}
void search_ans(int used,int now)//used表示已经使用过的炸弹数，now表示now之前的武器都已经被炸毁
{
if (used+perfect[now]>=ans) return;//如果当前已经使用过的炸弹加上now---m的最少使用炸弹数>=ans则退出.
if (now==m+1)//如果已经炸掉了所有的武器则更新答案。
{
ans=used;
return;
}
int tempa[l],tempb[l],maxl=now-1;//开始划分这一段的区间。
memset(vis,false,sizeof(vis));
head=tail=0;
for (int i=1;i<=n;i++)
if (b[i]==0) //没有被使用过则入队。
{
vis[i]=true;
dl[++tail]=i;
}
while (head<tail) { int k=dl[++head];//取出在队中的炸弹 if (maxl<MAXT[now][k])//如果这个炸弹从now开始能够炸到更大的编号则更新 maxl=MAXT[now][k]; for (int i=1;i<used;i++)//回过头来查看原先使用过的炸弹，看看能否用匈牙利算法的思路改变原来的匹配，获得更大的值。 if (g[i][k] && !vis[a[i]]) { vis[a[i]]=true; dl[++tail]=a[i]; } } if (maxl==now-1) return;//如果已经不能完成匹配了就结束。 used++; memcpy(g[used],can[now][maxl],sizeof(can[now][maxl]));//左边是区间，右边是炸弹，表示可以使用这些炸弹炸掉这段区间，因此连边。 memcpy(tempa,a,sizeof(a));//用于回溯 memcpy(tempb,b,sizeof(b)); memset(vis,false,sizeof(vis));//匈牙利算法的判重 xiongyali(used);//给used这个点匹配。 for (int i=maxl;i>=now;i--)//从大到小枚举区间。增强perfect数组的作用。
{
memcpy(g[used],can[now][i],sizeof(can[now][i]));
search_ans(used,i+1);
}
memcpy(a,tempa,sizeof(a));
memcpy(b,tempb,sizeof(b));
}
void output_ans()
{
printf("%d\n",ans);
}
int main()
{
input_data();
pre();
search_ans(0,1);
output_ans();
return 0;
}

-2

FlameH LV 10 @ 2016-03-16 21:45:57

因为题目描述里有**数据随机生成** 所以大数据直接输出DP结果就能拿(pian)满...O(n^2)
当然数据强的话就不一定能过了

-2

琉璃盏 LV 10 @ 2015-01-07 18:42:54

#include <cstdio>

#include <cstring>

#include <cstdlib>

#define l 110

int x1[l],y1[l],x2[l],y2[l],m,n,k,MAXT[l][l],ans=1000000000,a[l],b[l],vis[l],dl[l],head,tail,perfect[l];

bool reach[l][l],can[l][l][l],g[l][l];

void input_data()//读入数据

{

scanf("%d%d%d",&m,&n,&k);

for (int i=1;i<=m;i++)

scanf("%d%d",&x1[i],&y1[i]);

for (int i=1;i<=n;i++)

scanf("%d%d",&x2[i],&y2[i]);

for (int i=1;i<=m;i++)

for (int j=1;j<=n;j++)

reach[i][j]=((x1[i]-x2[j])*(x1[i]-x2[j])+(y1[i]-y2[j])*(y1[i]-y2[j]))<=(k*k);//reach[i][j]表示i号武器能否被j号炸弹炸到。

}

void pre()

{

for (int i=1;i<=m;i++)

{

for (int j=1;j<=n;j++)

can[i][i][j]=reach[i][j];//can[i][j][k]表示k号炸弹是否能炸毁i-j号武器

for (int j=i+1;j<=m;j++)

for (int d=1;d<=n;d++)

can[i][j][d]=can[i][j-1][d] && reach[j][d];//更新

for (int j=1;j<=n;j++)

{

MAXT[i][j]=i-1;//MAXT[i][j]表示j号炸弹从i号武器开始能够炸到的最大编号

for (int d=i;d<=m;d++)

if (can[i][d][j]) MAXT[i][j]=d;//利用can数组来更新MAXT数组

}

}

perfect[m+1]=0;//perfect[i]表示i-m号武器最少需要多少个炸弹才能炸掉(可以重复使用炸弹);

for (int i=m;i>=1;i--)

{

int t=i-1;

for (int j=1;j<=n;j++)

if (MAXT[i][j]>t) t=MAXT[i][j];//找到这个炸弹的最大使用限度。

perfect[i]=perfect[t+1]+1;//从t+1转移到当前状态。

}

}

bool xiongyali(int x)//匈牙利算法

{

for (int i=1;i<=n;i++)

if (g[x][i] && !vis[i])

{

vis[i]=true;

if (b[i]==0 || xiongyali(b[i]))

{

a[x]=i;

b[i]=x;

return true;

}

}

return false;

}

void search_ans(int used,int now)//used表示已经使用过的炸弹数，now表示now之前的武器都已经被炸毁

{

if (used+perfect[now]>=ans) return;//如果当前已经使用过的炸弹加上now---m的最少使用炸弹数>=ans则退出.

if (now==m+1)//如果已经炸掉了所有的武器则更新答案。

{

ans=used;

return;

}

int tempa[l],tempb[l],maxl=now-1;//开始划分这一段的区间。

memset(vis,false,sizeof(vis));

head=tail=0;

for (int i=1;i<=n;i++)

if (b[i]==0) //没有被使用过则入队。

{

vis[i]=true;

dl[++tail]=i;

}

while (head<tail)
{
int k=dl[++head];//取出在队中的炸弹
if (maxl<MAXT[now][k])//如果这个炸弹从now开始能够炸到更大的编号则更新
maxl=MAXT[now][k];
for (int i=1;i<used;i++)//回过头来查看原先使用过的炸弹，看看能否用匈牙利算法的思路改变原来的匹配，获得更大的值。
if (g[i][k] && !vis[a[i]])
{
vis[a[i]]=true;
dl[++tail]=a[i];
}
}
if (maxl==now-1) return;//如果已经不能完成匹配了就结束。
used++;
memcpy(g[used],can[now][maxl],sizeof(can[now][maxl]));//左边是区间，右边是炸弹，表示可以使用这些炸弹炸掉这段区间，因此连边。
memcpy(tempa,a,sizeof(a));//用于回溯
memcpy(tempb,b,sizeof(b));
memset(vis,false,sizeof(vis));//匈牙利算法的判重
xiongyali(used);//给used这个点匹配。
for (int i=maxl;i>=now;i--)//从大到小枚举区间。增强perfect数组的作用。

{

memcpy(g[used],can[now][i],sizeof(can[now][i]));

search_ans(used,i+1);

}

memcpy(a,tempa,sizeof(a));

memcpy(b,tempb,sizeof(b));

}

void output_ans()

{

printf("%d\n",ans);

}

int main()

{

input_data();

pre();

search_ans(0,1);

output_ans();

return 0;

}

-2

一方T行 LV 10 @ 2014-03-22 18:34:55

BFS之渣渣水题

一方T行 @ 2014-03-22 19:55:44

额，发错了。

-2

xuketian LV 9 @ 2010-03-15 21:51:50

搜索+最优化剪枝+可行性剪枝+二分图匹配+动态规划

- - Orz ACRush！

-2

qiaomingda LV 8 @ 2010-03-07 17:12:55

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

强烈orz楼天城教主的论文。。。

-2

徐晨阳 LV 4 @ 2009-10-22 16:20:50

做的头晕茫茫了。。。

-2

lida LV 8 @ 2009-10-21 19:21:40

吃一堑长一智啊!

-2

玛维-影之歌 LV 10 @ 2009-10-15 20:52:53

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

卡时间+傻剪枝+后效性DP也能过...

-2

yxy LV 10 @ 2009-08-10 21:58:59

搞了那么长时间

-2

lirenjue LV 10 @ 2009-08-02 10:42:28

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

-2

董 LV 10 @ 2009-07-31 13:07:06

http://hi.baidu.com/%CB%D5%CC%DAsauterne

-2

sijin LV 3 @ 2009-07-26 16:00:19

-2

wu3412790 LV 10 @ 2009-07-22 10:59:18

正着搜，T三个点，反着搜，0MS AC。。。。

-2

578559967 LV 10 @ 2009-07-20 18:45:59

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

-2

323232 LV 3 @ 2006-11-11 16:28:51

参见楼天城WC2004论文

-3

PowderHan LV 10 @ 2017-05-07 12:50:56

/*
楼天城浅谈部分搜索+高效算法在搜索问题中的应用论文不解释~
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const int maxm=100+2;
const int maxn=100+2;

int n,m,dist[maxm],MaxT[maxm][maxn];
bool reachable[maxm][maxn],*can[maxm][maxm];
/*
m=B国武器数。
n=A国炸弹数。
dist[i]=如果A国炸弹可以重复使用，炸掉B国武器I~m的最少使用炸弹数。
MaxT[s][i]=炸弹I，从S开始炸，可以炸到的最大编号，
           如果炸弹I炸不到S，则MaxT[I][S]=S-1。
reachable[i][j]=A国炸弹i是否可以炸到B国炸弹j。
can[s][t][i]=表示A国炸弹I是否可以炸到B国武器S,S+1..T-1,T。
*/
int answer,bestv[maxn];
/*
answer=最少需要的A国炸弹数。
bestv=记录取最优解A国炸弹的使用序列。
*/
int a[maxm],b[maxn];
bool vis[maxn],*g[maxm];
/*
a[i],b[i]用于匹配，分别记录左（右）第i个点的匹配边的另一个点的编号，如果没有匹配则为0。
vis[i]用于匹配和宽度优先搜索时判重。
g[i][j]=左边第i个点到右边第j个点是否有边。
*/
void init()
{
    //读入数据并计算reachable。
    int x1[maxm],y1[maxm],x2[maxn],y2[maxn],i,j,R;
    scanf("%d%d%d",&m,&n,&R);
    for (i=1;i<=m;i++)
        scanf("%d%d",&x1[i],&y1[i]);
    for (i=1;i<=n;i++)
        scanf("%d%d",&x2[i],&y2[i]);
    for (i=1;i<=m;i++)
        for (j=1;j<=n;j++)
            reachable[i][j]=((x1[i]-x2[j])*(x1[i]-x2[j])+(y1[i]-y2[j])*(y1[i]-y2[j])<=R*R);
}
void preprocess()
{
    //初始化，计算can,MaxT。
    int s,t,i;
    for (i=1;i<=m;i++)
        g[i]=new bool[maxn];
    for (s=1;s<=m;s++)
        for (t=s;t<=m;t++)
            can[s][t]=new bool[maxn];
    for (s=1;s<=m;s++)
    {
        for (i=1;i<=n;i++)
            can[s][s][i]=reachable[s][i];
        for (t=s+1;t<=m;t++)
            for (i=1;i<=n;i++)
                can[s][t][i]=can[s][t-1][i] && reachable[t][i];
        for (i=1;i<=n;i++)
        {
            MaxT[s][i]=s-1;
            for (t=s;t<=m;t++)
                if (can[s][t][i])
                    MaxT[s][i]=t;
        }
    }
    //计算dist
    dist[m+1]=0;
    for (s=m;s>=1;s--)
    {
        t=s-1;
        for (i=1;i<=n;i++)
            if (MaxT[s][i]>t)
                t=MaxT[s][i];
        dist[s]=1+dist[t+1];
    }
}
bool find(int v)
{
    //匈牙利算法找可增广路。
    for (int i=1;i<=n;i++)
        if (g[v][i] && !vis[i])
        {
            vis[i]=true;
            if (b[i]==0 || find(b[i]))
            {
                a[v]=i;
                b[i]=v;
                return true;
            }
        }
    return false;
}
void search(int used,int s)
{
    //状态：已经使用了used个A国炸弹，编号在s之前的B国武器都已经炸毁。
    
    if (used+dist[s]>=answer)//优化一：最优性剪枝
        return;
    if (s==m+1)
    {
        //如果B国武器已经全部炸毁，更新最优解，回溯。
        answer=used;
        return;
    }
    int t,maxL,tempa[maxm],tempb[maxn],op,cl,queue[maxn],k,i;
    //宽度优先搜索计算出下一个划分的最大长度maxL
    memset(vis,false,sizeof(vis));
    maxL=s-1;
    op=cl=0;
    for (i=1;i<=n;i++)
        if (b[i]==0)
        {
            vis[i]=true;
            queue[++op]=i;
        }
    while (cl<op)
    {
        k=queue[++cl];
        if (MaxT[s][k]>maxL)
            maxL=MaxT[s][k];
        for (i=1;i<=used;i++)
            if (g[i][k] && !vis[a[i]])
            {
                vis[a[i]]=true;
                queue[++op]=a[i];
            }
    }
    if (maxL==s-1)
        return;
    used++;
    memcpy(tempa,a,sizeof(a));
    memcpy(tempb,b,sizeof(b));
    memset(vis,false,sizeof(vis));
    g[used]=can[s][maxL];
    //扩展交错路。
    find(used);
    //从大到小枚举下一段的长度。
    for (t=maxL;t>=s;t--)
    {
        g[used]=can[s][t];
        search(used,t+1);
    }
    memcpy(a,tempa,sizeof(a));
    memcpy(b,tempb,sizeof(b));
}
void out()
{
    //输出结果。
    printf("%d\n",answer);
}
int main()
{
    init();
    preprocess();
    answer=1000000000;
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    search(0,1);
    out();
    return 0;
}

题解

37 条题解

智破连环阵

信息

状态

开发

支持

题解

37 条题解

智破连环阵

信息

状态

开发

支持

还没有账户？

登录