TopCoder SRM 667 Div1 Problem 250 - OrderOfOperations (状压dp)
## 题意 ##
给出一些01串，我们的目标是选中全部的位置。
每选择一个串，如果那个串中的1的位置之前没被选过，cnt++。统计完之后，ans += cnt^2。
问如何选择串的顺序，使得最后的值最小。
## 思路 ##
一开始去想贪心了，乱搞了好一会儿也搞不出来。
感觉这题用循环写dp比用记忆化要方便一点。
我们用dp[state]表示state状态所用的最小值。
| dp[cur_state | another_state] = min(self, diff(cur_state, another_state)) |
意思是对于当前的状态cur_state，枚举s中的全部状态another_state，新的状态通过cur_state加上它们之间的差值来转移。
## 代码 ##
class OrderOfOperations {
public:
int dp[1<<21], val[100];
int minTime(vector<string> s) {
MS(dp, INF); MS(val, 0);
dp[0] = 0;
int all = 0;
for (int i = 0; i < SZ(s); i++)
{
for (int j = 0; j < SZ(s[i]); j++) val[i] |= ((s[i][j]-'0')<<j);
all |= val[i];
}
for (int i = 0; i <= all; i++) if (dp[i] != INF)
{
int cur = __builtin_popcount(i);
for (int j = 0; j < SZ(s); j++)
{
int tar = i | val[j];
int cnt = __builtin_popcount(tar);
if (tar != i) dp[tar] = min(dp[tar], dp[i]+(cur-cnt)*(cur-cnt));
}
}
return dp[all];
}
};