递推DP 赛码 1005 Game-白红宇

递推DP 赛码 1005 Game

阅读量：6586 次

发布时间：2019-06-24

本文共 1077 字，大约阅读时间需要 3 分钟。

1 /* 2     递推DP：官方题解 3         令Fi,j代表剩下i个人时，若BrotherK的位置是1，那么位置为j的人是否可能获胜 4         转移的时候可以枚举当前轮指定的数是什么，那么就可以计算出当前位置j的人在剩下i − 1个人时的位置 5         （假设BrotherK所处的位置是1），然后利用之前计算出的F值判定此人是否可能获胜 6         时间复杂度为O(n3) 7     dp[i][j] 表示有i个人，j位置的人是否可能胜利。dp[1][0] = 1;    cnt = sum (dp[n][i]); 8     有最优化子结构，i个人可以由i-1个人的情况中每个能胜利的位置再走一步 9     取余小技巧：0~n-110 */11 #include 
     
      12 #include 
      
       13 #include 
       
        14 #include 
        
         15 #include 
         
          16 #include 
          17 #include 
           
            18 #include 
            
             19 #include 
             
              20 #include 
              
               21 using namespace std;22 23 const int MAXN = 2e2 + 10;24 const int INF = 0x3f3f3f3f;25 int dp[MAXN][MAXN];26 int s[MAXN];27 28 int main(void) //赛码 1005 Game29 {30 //freopen ("E.in", "r", stdin);31 32 int t, n, m;33 scanf ("%d", &t);34 while (t--)35 {36 scanf ("%d%d", &n, &m);37 for (int i=1; i<=m; ++i)38 {39 scanf ("%d", &s[i]);40 }41 memset (dp, 0, sizeof (dp));42 dp[1][0] = 1;43 44 for (int i=2; i<=n; ++i)45 {46 for (int j=0; j