100問マラソン 5問目 SRM 667 Div2 Med: OrderOfOperationsDiv2

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13988&rd=16547

解法

dpらしい．div2Medだし貪欲だろうと高をくくっていたら駄目でした．

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int dp[1<<21];
class OrderOfOperationsDiv2{
public:
	int minTime(vector<string> s){
		for(int i=0;i<(1<<20);i++)dp[i] = 1e9;
		vector<int> bit(s.size());
		int ok=0;
		for(int i=0;i<s.size();i++){
			int tmp = 0;
			for(int j=0;j<s[i].size();j++){
				tmp <<= 1;
				if(s[i][j] == '1')tmp += 1;
			}
			bit[i] = tmp;
			ok |= tmp;
		}
		
		dp[0] = 0;
		int n = s[0].size();
		for(int i=0;i<s.size();i++){
			for(int k=0;k<(1<<n);k++){
				if(dp[k] == 1e9)continue;
				for(int j=0;j<s.size();j++){
					int l = __builtin_popcount(~k & bit[j]);
					dp[( k | bit[j] )] = min( dp[(k | bit[j])], dp[k] + l*l );
				}
			}
		}
		
		int ret = 1e9;
		for(int i=0;i<(1<<n);i++){
			if( (i&ok) == ok){ 
				ret = min(ret,dp[i]);
			}
		}
			
		return ret;
	}
};