背包dp问题的变体，每一关看成一个背包，用的炸弹数看成重量，通关概率看成物品总价值，然后本关与之前所有关卡用的炸弹数最优分配用分类讨论。注意到若用100个炸弹则必定通关，那么枚举100个或剪枝都行。时间复杂度为o(100nm),最多正好是十的八次方。

 

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 double dp[1005][1001];//dp[a][b]代表通a关用b个炸弹的最大通过概率 6  7 struct level { 8     int k, b; 9 };10 11 double min(double a, double b)12 {13     return a < b ? a : b;14 }15 16 double max(double a, double b)17 {18     return a > b ? a : b;19 }20 21 double mayPoint(int k, int b, int x)22 {23     return min(1, double(k*x + b) / (double)100);24 }25 26 27 int main()28 {29     int n, m;30     scanf("%d%d",&n,&m);31     vector
         
           levels(n+1);32     for (int i = 1; i <= n; ++i)33     {34         int k, b;35         scanf("%d%d", &k, &b);36         levels[i].b = b;37         levels[i].k = k;38     }39     for (int i = 0; i <= m; ++i)40     {41         dp[0][i] = 1;42     }43     for (int i = 1; i <= n; ++i)44     {45         for (int nb = 0; nb <= m; ++nb)46         {47             for (int b = nb; b <= m; ++b)48             {49                 dp[i][b] = max(dp[i][b], dp[i - 1][b - nb] * mayPoint(levels[i].k, levels[i].b, nb));50             }51             if (mayPoint(levels[i].k, levels[i].b, nb) >= 1)break;52         }53     }54     for (int i = 0; i <= n; ++i)55     {56         for (int j = 0; j <= m; ++j)57         {58             cout << dp[i][j] << "\t";59         }60         cout << endl;61     }62     printf("%lf\n", dp[n][m]);63     64 }
         
        
       
      

（卡了一个小时最后还没做出来，菜swl）