1 条题解

  • 4
    @ 2024-1-26 19:59:31

    什么贪心,无非是一道被埋在角落里的递归型枚举罢了,时间复杂度 O(20×220)O(20\times2^{20}) ,可以过。

    #include<bits/stdc++.h>
    using namespace std;
    int a[30],ans=2147483647;
    void work(int dep,int sum){
    	if(dep>20){
    		for(int i=1;i<=20;i++){
    			if(a[i])return;
    		}
    		ans=min(ans,sum);
    		return;
    	}
    	work(dep+1,sum);
    	a[dep-1]=!a[dep-1],a[dep]=!a[dep],a[dep+1]=!a[dep+1];
    	work(dep+1,sum+1);
    	a[dep-1]=!a[dep-1],a[dep]=!a[dep],a[dep+1]=!a[dep+1];
    }
    int main(){
    	ios::sync_with_stdio(false);
    	cin.tie(0),cout.tie(0);
    	for(int i=1;i<=20;i++){
    		cin>>a[i];
    	}
    	work(1,0);
    	cout<<ans;
    	return 0;
    }
    
    
    • 1

    信息

    ID
    384
    时间
    1000ms
    内存
    64MiB
    难度
    2
    标签
    递交数
    97
    已通过
    21
    上传者