贪心|001:特殊密码锁（贪心）贪心|枚举

http://cxsjsxmooc.openjudge.cn/2018t2winterw1/001/
这道题不难，可以枚举来写，每个锁两种状态一共30个锁2^30的复杂度可能不会超，在此提供另外一种贪心的思路。
对于第一个锁，我们枚举（好吧算不上枚举）开或不开两种情况。如果第一个锁不为目标状态，那么只有第二个锁才能关掉它。。。依次类推，如果第i个锁不为目标状态，那么只有第i+1个锁才能关掉它
最后，我们只用判断最后一个锁是否为目标状态即可

#include #include #include #include using namespace std; const int maxn = 35; int srcCode[maxn], desCode[maxn]; int len = 1; int solve(int i1) { //第一个按钮按或不按时的最优解，无解返回1<<30 int step = 0, tmp[maxn]; if(i1) step++; for(int i = 1; i <= len; i++) tmp[i] = srcCode[i]; tmp[1] ^= i1; tmp[2] ^= i1; //按或不按第一个按钮 for(int i = 1; i < len; i++) if(tmp[i] != desCode[i]){ //如果第i个按钮不为目标状态，按下第i+1个按钮 tmp[i] ^= 1, tmp[i+1] ^= 1, tmp[i+2] ^= 1; step++; }if(tmp[len] == desCode[len]) return step; //符合情况 else return 1<<30; //不符合情况 }int main() { char input[maxn]; memset(input, 0, sizeof(input)); gets(input); for(len = 0; input[len]!=0; len++) srcCode[len+1] = input[len]-'0'; gets(input); for(len = 0; input[len]!=0; len++) desCode[len+1] = input[len]-'0'; int ans = min(solve(1), solve(0)); //取第一个按钮按或不按的最优解即可 if(ans < 1<<30) printf("%d\n",ans); else printf("impossible\n"); return 0; }

【贪心|001:特殊密码锁（贪心）】