Loading...

洛谷P3943 星空

check评论:0 条 remove_red_eye浏览量:412 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-07-11

解法0:
我会$rand$!小于四的答案随便猜

预计得分8

解法0.5:
我会输出$2$!

预计得分12(233......)

解法1:
看到有$m=1$的时候,直接从左到右扫一遍xjb贪心一波,其他还是$rand$

预计得分28

解法2:
我会状压!直接状压扫一遍

预计得分24~28

解法3:
考虑到$k$很小,就从这个方向来思考:

比如对于一串数列$1,0,1,0,1,1,0$($1$表示亮着$0$表示不是亮的)

我们将其两边扩展各一个$0$ $->$ $0,1,0,1,0,1,1,0,0$

然后对其扫一遍,形成一个原数组的“异或数组”
即值分别为$1,1,1,1,1,0,1,0$

既然要将原数组全部都变为$0$,区间翻转也不会改变其相邻的异或值,则想到只需要将不同的异或值反转到一起消除即可

$Q$:为什么加$0$

$A$:$0$^$a=a$

则问题转化为了一个$01$数列,若两个$1$在一起即可消除,要翻转至少多少次

每次暴力去求

预计得分24(233...白考虑了)

解法4:
继续解法3,不要前功尽弃

可以非常非常容易的想到,这可以转化为图论来解,只要对两两点对之间跑$SPFA$即可

$Q$:不会超时吗

$A$:你是不是没看到$K \leq 8$...

于是问题解决完毕,接下来就是经典的状压dp可做的了

code:

#include<bits/stdc++.h>
using namespace std;
int way[65],a[40010],b[40010],pos[18],dis[18][18],cnt;
int n,m,k;
int que[40005],vis[40005],tim[40005],dp[70005],ycl[70005];
queue<int> q;
void bfs(int x)
{
    int hd=0;
    memset(vis,0,sizeof(vis));
    memset(tim,0,sizeof(tim));
    q.push(x);
    vis[x]=1;
    tim[x]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=1;i<=m;i++)
        {
            int v1=u+way[i],v2=u-way[i];
            if(v1<=n&&vis[v1]==0)
            {
                q.push(v1);
                tim[v1]=tim[u]+1;
                vis[v1]=1;
            }
            if(v2>=0&&vis[v2]==0)
            {
                q.push(v2);
                tim[v2]=tim[u]+1;
                vis[v2]=1;
            }
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&k,&m);
    for(int i=1;i<=k;i++)
    {
        int x;
        scanf("%d",&x);
        a[x]=1;
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&way[i]);
    }
    for(int i=0;i<=n;i++)
    {
        b[i]=a[i]^a[i+1];
        if(b[i]==1)
        {
            pos[++cnt]=i;
        }
    }
    for(int i=1;i<=cnt;i++)
    {
        bfs(pos[i]);
        for(int j=1;j<=cnt;j++)
        {
            dis[i][j]=tim[pos[j]];
        }
    }
    for(int zt=0;zt<(1<<cnt);zt++)
    {
        ycl[zt]=cnt;
        for(int k=1;k<=cnt;k++)
        {
            if(((zt>>(k-1))&1)==0)
            {
                ycl[zt]=k;
                break;
            }
        }
    }
    for(int zt=1;zt<(1<<cnt);zt++)
    {
        dp[zt]=1e8;
    }
    dp[0]=0;
    for(int zt=0;zt<(1<<cnt);zt++)
    {
        for(int i=ycl[zt]+1;i<=cnt;i++)
        {
            if(((zt>>(i-1))&1)==0&&dis[ycl[zt]][i]!=0)
            {
                dp[zt|(1<<(ycl[zt]-1))|(1<<(i-1))]=min(dp[zt|(1<<(ycl[zt]-1))|(1<<(i-1))],dp[zt]+dis[ycl[zt]][i]);
            }
        }
    }
    printf("%d",dp[(1<<cnt)-1]);
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名