題意：
 |
| 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的方向去想，搞死了搞不出來，今天洗澡的時候忽然發(fā)現(xiàn)。。這題原來是一個水了不能再水的DP
首先，設(shè)置DP狀態(tài)(pos,left,jud)，即決策到第pos個人時還允許有l(wèi)eft個人是騙子，并且第pos個人是誠實的/騙子時的狀態(tài)。
狀態(tài)是一個集合，我用的bitset。
關(guān)于狀態(tài)轉(zhuǎn)移就很簡單了
分2種情況：
1、第pos個人是騙子，那么第pos+1個人是誠實的或者騙子都可以
2、第pos個人是誠實的，那么第pos+1個人只能根據(jù)第pos個人說的話來決定
第一個人的情況要枚舉，并且最后特別判斷下
還有就是，集合初始化為全1，然后狀態(tài)的運算是與運算。注意滾動數(shù)組，不然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
}