题意：
 |
| i (tester) |
j (testee)/td> |
test outcome ai,j |
| truth-teller |
truth-teller |
0 |
| truth-teller |
liar |
1 |
| liar |
truth-teller |
0 or 1 |
| liar |
liar |
0 or 1 |
|
不用说了吧
解法：
这题我开始往2-sat的方向去想，搞死了搞不出来，今天洗澡的时候忽然发现。。这题原来是一个水了不能再水的DP
首先，设置DP状态(pos,left,jud)，即决策到第pos个人时还允许有left个人是骗子，并且第pos个人是诚实的/骗子时的状态。
状态是一个集合，我用的bitset。
关于状态转移就很简单了
分2种情况：
1、第pos个人是骗子，那么第pos+1个人是诚实的或者骗子都可以
2、第pos个人是诚实的，那么第pos+1个人只能根据第pos个人说的话来决定
第一个人的情况要枚举，并且最后特别判断下
还有就是，集合初始化为全1，然后状态的运算是与运算。注意滚动数组，不然MLE到你哭~
代码：
1
# include <cstdio>
2# include <cstring>
3# include <bitset>
4using namespace std;
5# define N 1005
6bitset<N> dp[2][N][2],one,zero;
7int data[N],n,maxnum;
8int main()
9
{
10
int test;
11 scanf("%d",&test);
12 one.set();
13 zero.reset();
14 while(test--)
15
{
16 one.set();
17 zero.reset();
18 scanf("%d%d",&n,&maxnum);
19 for(int i=0;i<n;i++)
20 scanf("%d",data+i);
21 bitset<N> res=one;
22 for(int i=0;i<=maxnum;i++)
23 dp[0][i][0]=zero,dp[0][i][1]=one;
24 for(int i=1;i<=n;i++)
25 {
26 for(int j=0;j<=maxnum;j++)
27 dp[i%2][j][0]=dp[i%2][j][1]=one;
28 for(int j=0;j<=maxnum;j++)
29 dp[i%2][j][0]&=dp[(i-1)%2][j][1];
30 for(int j=0;j<maxnum;j++)
31 dp[i%2][j][1]&=dp[(i-1)%2][j+1][1].set(i);
32 if(!data[i-1])
33 for(int j=0;j<=maxnum;j++)
34 dp[i%2][j][0]&=dp[(i-1)%2][j][0];
35 else
36 for(int j=0;j<maxnum;j++)
37 dp[i%2][j][1]&=dp[(i-1)%2][j+1][0].set(i);
38
}
39 for(int i=0;i<=maxnum;i++)
40 res&=dp[n%2][i][0];
41
42 for(int i=0;i<maxnum;i++)
43 dp[0][i][0]=one,dp[0][i][1]=zero.set(0);
44 dp[0][maxnum][0]=dp[0][maxnum][1]=one;
45 for(int i=1;i<=n;i++)
46 {
47 for(int j=0;j<=maxnum;j++)
48 dp[i%2][j][0]=dp[i%2][j][1]=one;
49 for(int j=0;j<=maxnum;j++)
50 dp[i%2][j][0]&=dp[(i-1)%2][j][1];
51 for(int j=0;j<maxnum;j++)
52 dp[i%2][j][1]&=dp[(i-1)%2][j+1][1].set(i);
53 if(!data[i-1])
54 for(int j=0;j<=maxnum;j++)
55 dp[i%2][j][0]&=dp[(i-1)%2][j][0];
56 else
57 for(int j=0;j<maxnum;j++)
58 dp[i%2][j][1]&=dp[(i-1)%2][j+1][0].set(i);
59 }
60 for(int i=0;i<maxnum;i++)
61 res&=dp[n%2][i][1];
62
63
64 if(res.count()==0) printf("0 0\n");
65 else
66 {
67 int pos=-1;
68 for(int i=0;i<n&&pos==-1;i++)
69 if(res[i])
70 pos=i;
71 printf("%d %d\n",res.count(),pos+1);
72 }
73 }
74 return 0;
75
}