GroupBlog

1659: [Usaco2006 Mar]Lights Out 关灯

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 315 Solved: 81
[ Submit][ Status][ Discuss]

Description

奶牛们喜欢在黑暗中睡觉。每天晚上，他们的牲口棚有L（3<=L<=50）盏灯，他们想让亮着的灯尽可能的少。他们知道按钮开关的位置，但喜闻乐见的是他们并没有手指。你得到了一个长度为T（1<=T<=7）的插槽用以帮助奶牛们改变灯的状态。

Input

第一行，两个整数L和T。第二行给出一个长度为L的01串表示初始灯的状态，0表示灯是灭的，1表示灯是亮的。第三行给出一个长度为T的01串，表示你获得的插槽。

Output

第一行输出一个整数K，表示在满足亮着的灯最少的情况下，你要用插槽操作的次数。第二行到第K+1行，每行一个整数表示你的插槽使用的位置。

"K最小的解，并且满足解的字典序最大（即按钮开关的位置尽可能靠后）"

Sample Input

10 4
1111111111
1101

Sample Output

5
1
3
4
6
7

HINT

使用5次插槽

1111111111 初始状态

0010111111 对第一个位置使用插槽

0001101111 对第三个位置使用插槽

0000000111 对第四个位置使用插槽

0000011101 对第六个位置使用插槽

0000010000 对第七个位置使用插槽

可以证明这是满足字典序最小的最优解。

Source

Silver

刚开始想的是状压dp 但状压状态数太多,2^50个,肯定超时,

后来看到了迭代加深搜索,枚举剩余灯亮的数,这就给其进行了限定,是一个很好的剪枝

感觉迭代加深搜索可以用在状态数特别多的搜索中.

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int INF = 1e9;




int n,m;
bool a[100];
bool b[100];
char sa[100];
char sb[100];
int maxd;
int path[100];
int len=1e9;
int stk[100];
int top=0;



bool dfs(int pos , int light)
{
//    cout << pos<<" "<<light<<endl;
    int fl=0;

    if(light>maxd)
    {
        return false;
    }
    if(pos+m-1>=n)
    {
        for(int i=pos;i<n;i++)
        {
            light+=a[i];
        }
        if(light>maxd)
        {
            return false;
        }


        if(top>=len) return true;
        len=top;
        for(int i=0;i<top;i++)
        {
            path[i] = stk[i];
        }
        return true;
    }


    fl |= dfs(pos+1,light+a[pos]);

    stk[top++]=pos;
    for(int i=0;i<m;i++) a[pos+i] = b[i] ^ a[pos+i];
    fl |= dfs(pos+1,light+a[pos]);
    top--;
    for(int i=0;i<m;i++) a[pos+i] = b[i] ^ a[pos+i];

    return fl;
}



int main()
{
//    freopen("data.txt","r",stdin);
//    ios_base::sync_with_stdio(false);
    scanf("%d%d",&n,&m);
    scanf("%s%s",sa,sb);

    for(int i=0;i<n;i++)
    {
        if(sa[i]=='1')
        {
            a[i]=1;
        }
    }

    for(int i=0;i<m;i++)
    {
        if(sb[i]=='1')
        {
            b[i]=1;
        }
    }

    for(maxd=0;maxd<=n;maxd++)
    {
        if(dfs(0,0))
        {
            break;
        }
    }

    printf("%d\n",len);
    for(int i=0;i<len;i++)
    {
        printf("%d\n",path[i]+1);
    }
    return 0;
}