SRM667 Div.2 Med

本番中は貪欲法で実装しテストに通ったのでそのままサブミットした。

貪欲法でだめなケースはこちら

{"0011","1100","1110"}　

逆に貪欲法で駄目なの気づいてれば大量虐殺できていい順位に慣れただろうなと。

じゃあ実際にはどうやるのかというとbitDPとかダイクストラ法とかをやる。今回はbitDPで実装した。計算量はO(2^m*n)くらい。

dp[i] = 0..0からiになるまでにかかるコストの最小値とすると、

bit[j] =  s[i]をbitで表したもの

dp[i | bit[j] ] = min(dp[ i | bit[j] ], dp[j] + __buildin_popcount( (i | bit[j] ) ^ i)の二乗 ;

という風になる。

class OrderOfOperationsDiv2{
	public:
	int dp[1<<20];
	int minTime(vector<string> s) {
		int n=s.size();
		int m=s[0].size();
		int bit[n];fill(bit,bit+n,0);
		REP(i,n)REP(j,m){
			if(s[i][j]=='1') bit[i] |= (1<<j);
		}
		fill(dp,dp+(1<<20),INF);
		dp[0]=0;
		REP(i,1<<m){
			REP(j,n){
				int nex=i|bit[j];
// 				DEBUG(bit[j]);
				bitset<20> bs((unsigned long)(nex^i));
				int cnt=bs.count();
				dp[nex] = min(dp[nex],dp[i] + cnt*cnt);
			}
		}
// 		REP(i,1<<m)DEBUG(dp[i]);
		int last=0;
		REP(i,n) last|=bit[i];
		return dp[last];
	}
	

};