[MSSB]缩小枚举范围后的简易递推
特征
每一个位置顶多只会操作一次。如果操作两次的话，相当于不操作，必然不满足最优解
在一套方案中，操作的顺序无关紧要
如果我们确定了第1行的操作方案的话，那么后面的行数都可以依此递推
解法
枚举第一行的操作方案，然后依次递推
时间复杂度为\(O(1<<len(1))\)
题目
费解的开关
#include <bits/stdc++.h>
using namespace std;
int n,m,i,j,k,a[7][7],ans1=1e6,b[7][7];
int main()
{
int n;
cin>>n;
while(n--)
{
getchar();
for (i=1;i<=5;i++)
{
for (j=1;j<=5;j++)
{
char ch=getchar();
b[i][j]=ch-'0';
}
getchar();
}
for (i=0;i<=(1<<5);i++)
{
for (j=1;j<=5;j++)
{
for (k=1;k<=5;k++)
a[j][k]=b[j][k];
}
int ans=0;
for (j=1;j<=5;j++)
if (i>>(j-1) & 1)
{
ans++;
a[1][j-1]^=1;
a[1][j+1]^=1;
a[1][j]^=1;
a[2][j]^=1;
}
for (j=1;j<=4;j++)
for (k=5;k>=1;k--)
if (!a[j][k])
{
ans++;
a[j][k]^=1;
a[j+2][k]^=1;
a[j+1][k]^=1;
a[j+1][k+1]^=1;
a[j+1][k-1]^=1;
}
bool ok=true;
for (j=1;j<=5;j++)
for (k=1;k<=5;k++)
if (!a[j][k])
ok=false;
if (ok)
ans1=min(ans1,ans);
}
if (ans1>6)
cout<<-1;
else
cout<<ans1;
ans1=1e7;
puts("");
}
return 0;
}翻转游戏
#include<bits/stdc++.h>
using namespace std;
#define loop(i,start,end) for(register int i=start;i<=end;++i)
#define anti_loop(i,start,end) for(register int i=start;i>=end;--i)
#define clean(arry,num) memset(arry,num,sizeof(arry))
#define ll long long
#define pd_one(pos,num) (((1<<(pos-1))&num)!=0)
#define copy(arry,arry2) memcpy(arry,arry2,sizeof(arry2))
template<typename T>void read(T &x){
x=0;char r=getchar();T neg=1;
while(r>'9'||r<'0'){if(r=='-')neg=-1;r=getchar();}
while(r>='0'&&r<='9'){x=(x<<1)+(x<<3)+r-'0';r=getchar();}
x*=neg;
}
int n;
const int maxn=20;
char MAP[maxn][maxn];
int G[maxn][maxn];
int op[maxn][maxn];
inline void reset(int x,int y){
op[x][y]^=1;
op[x-1][y]^=1;
op[x+1][y]^=1;
op[x][y+1]^=1;
op[x][y-1]^=1;
}
inline void printop(){
printf(">>>>>>>>>>>>>>>>>>>>>>>>printop\n");
loop(i,1,n){
loop(j,1,n)
printf("%d ",op[i][j]);
printf("\n");
}
}
inline bool judge(int a){
loop(i,1,n)
if(op[n][i]==a){
return false;
}
return true;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("datain.txt","r",stdin);
#endif
read(n);
loop(i,0,n-1)
scanf("%s",MAP[i]);
loop(i,1,n){
loop(j,1,n){
G[i][j]=(MAP[i-1][j-1]=='b')?1:0;
}
}
int result=INT_MAX;
for(int state=0;state<(1<<n);++state){
int res=0;
copy(op,G);
//printop();
loop(i,1,n){
if(pd_one(i,state)){
reset(1,i);
++res;
//printop();
}
}
//printop();
//printf("res:%d\n",res);
loop(i,1,n-1){//hang
loop(j,1,n){//lie
if(op[i][j]==0){
reset(i+1,j);
++res;
//printop();
}
}
}
if(judge(0))
result=min(res,result);
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
res=0;
copy(op,G);
loop(i,1,n){
if(pd_one(i,state)){
reset(1,i);
++res;
//printop();
}
}
loop(i,1,n-1){//hang
loop(j,1,n){//lie
if(op[i][j]==1){
reset(i+1,j);
++res;
//printop();
}
}
}
loop(i,1,n)
if(op[n][i]){
res=INT_MAX;
break;
}
if(judge(1))
result=min(res,result);
}
if(result<INT_MAX)
printf("%d\n",result);
else printf("Impossible\n");
return 0;
}1、读改善c#代码157个建议：建议1~3
2、iOS 所有设备一览 && CoreFoundation源码
3、设计数据仓库
4、jdbc,mybatis,hibernate各自优缺点及区别
5、GO模仿python –m SimpleHTTPServer 8080