题意:

给你一个全白的数组

你每次可以对连续ai个格子翻转,使得最终结果中k个格子是白色的(k<=10且给定哪些格子是白的)

求最小要几步

大概这题算法需要的比较多..

首先,我们看"连续翻转"一条

连续翻转一堆,不如"差分"

"差分" 即每次是否变化,如果变化了则记录"变化",没变化记录"没变",这样一个操作等于在两个点而不是一长条线上打tag了

所以..差分后..我们可以对这个玩意儿建图建边..

x到x+ai建边

所以图建好了,我们看某个点到另一个点的最短路

经过一条最短路,我们等于通过这一系列操作消去反应掉了一组

我们只要消掉所有组即可..这时候就可以写的2^(2k)的装压dp来处理这事儿了..

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[15];
int b[10005];
int dist[10005];
int c[25][25];
int dp[1<<20];
map<int,int> ma;
struct edge
{
    int y;
    edge * next;
};
edge * li[10005];
edge * new_edge()
{
    static edge a[2000005];
    static int top=0;
    return &a[top++];
}
void inserts(int x,int y)
{
    edge * t=new_edge();
    t->y=y;
    t->next=li[x];
    li[x]=t;
}
void insert_edge(int x,int y)
{
    inserts(x,y);
    inserts(y,x);
}
void bfs(int x)
{
    static int que[10005];
    int front=0,rail=1;
    que[0]=x;
    dist[x]=0;
    for (;front<rail;front++)
    {
        int now=que[front];
        edge * t;
        for (t=li[now];t!=0;t=t->next)
        {
            if (dist[t->y]==-1)
            {
                dist[t->y]=dist[now]+1;
                que[rail++]=t->y;
            }
        }
    }
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n,k,l;
    scanf("%d%d%d",&n,&k,&l);
    n++;
    int i;
    for (i=0;i<k;i++)
    {
        scanf("%d",&a[i]);
        b[a[i]-1]^=1;
        b[a[i]]^=1;
    }
    for (i=0;i<l;i++)
    {
        int x;
        scanf("%d",&x);
        int j;
        for (j=0;j<n-x;j++)
        {
            insert_edge(j,j+x);
        }
    }
    int sum=0;
    for (i=0;i<n;i++)
    {
        if (b[i])
        {
            ma[i]=sum++;
            memset(dist,-1,sizeof(dist));
            bfs(i);
            int j;
            for (j=0;j<i;j++)
            {
                if (b[j])
                {
                    c[ma[i]][ma[j]]=dist[j];
                    c[ma[j]][ma[i]]=dist[j];
                }
            }
        }
    }
    for (i=0;i<(1<<sum);i++)
    {
        dp[i]=1<<30;
    }
    dp[0]=0;
    for (i=0;i<(1<<sum);i++)
    {
        int j,k;
        for (j=0;j<sum;j++)
        {
            if (((1<<j)&i)) continue; 
            for (k=j+1;k<sum;k++)
            {
                if (((1<<k)&i)) continue;
                if (c[j][k]==-1) continue;
                dp[i^(1<<j)^(1<<k)]=min(dp[i^(1<<j)^(1<<k)],dp[i]+c[j][k]);
            }
        }
    }
    if (dp[(1<<sum)-1]>=(1<<29))
    {
        printf("-1\n");
    }
    else
    {
        printf("%d\n",dp[(1<<sum)-1]);
    }
    return 0;
}