Input
第一行包含一个整数 T，表示有 T 组测试数据。
接下来依次描述 T 组测试数据。对于每组测试数据：
第一行包含三个整数 n，m 和 k，含义同题目描述。
接下来 n 行，每行包含一个长度为 m 的只包含 ‘A’ 和 ‘B’ 的字符串，表示这份问卷对每个问题的回答。
保证
$$ 1 \leq T \leq 100 $$
$$ 1 \leq n \leq 10^3 $$
$$ 1 \leq m \leq 10 $$
$$ 1 \leq k \leq 10^6 $$
给定的 nn 份问卷互不相同。
Output
对于每组测试数据，输出一行信息 “Case #x: y”（不含引号），其中 x 表示这是第 xx 组测试数据，y 表示满足条件的问题集合的个数，行末不要有多余空格。
Sample Input
2
2 2 1
AA
BB
2 2 2
AA
BB
Sample Output
Case #1: 3
Case #2: 0
思路 >.<
下午才想起来今天百度之星预选要结束了，上去topcoder看看，随便选个AC率高的吧….
一看题目，懵逼，想了一会，还是用dp吧…
dp怎么做呢，枚举所有的题目可能呗….
那怎么枚举呢？
借助位运算呗，反正题目的要求最多10题，2^10也就1024，用二进制表示，1表示使用题目，0表示去除题目，如 1001 表示 题目4和题目1保留，那么对于答卷，我们只需要把答卷事先用下面的函数转换为数字，然后用数字的与运算计算即可：
int bit_trans(char * str, int length){
int s = 0;
for (int i = 0; i < length; i ++) {
s <<= 1;
s |= (str[i] -'A');
}
return s;
}就用 dp[i][j] 表示 第i行，第j题集，有多少个不同的运算对
首先看看：
TLE（超时）的代码
int main(){
int testCase = 1,n,m,k;
int T;
cin >> T;
char temp[10+1];
while (testCase <= T ) {
cin >> n >> m >> k;
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n ; i ++ ) {
cin >> temp;
seq[i] = bit_trans(temp, m);
}
int max_move = 1 << m;
for (int i = 1 ; i <= n; i ++ ) {
for (int j = 0 ; j < max_move ; j++ ) {
int S = seq[i] & j;
int diff = 0;
for (int k = 1; k <= i ; k ++) {
if( ( seq[k] & j ) == S ){
diff ++;
}
}
dp[i][j] = dp[i-1][j] + i - diff;
}
}
int ans = 0;
for (int i = 0; i < max_move; i ++) {
if(dp[n][i] >= k ){
ans ++;
}
}
cout<<"Case #"<<testCase<<": "<<ans<<endl;
testCase ++;
}
return 0;
}循环太多次了，其实内层k的循环可以存起来，
运算的时候，借助动态规划和填表的方法节省时间，代码如下
AC的代码
1 |
|