合唱团

题目链接： https://www.nowcoder.com/practice/661c49118ca241909add3a11c96408c8?tpId=85&tqId=29830&tPage=1&rp=1&ru=/ta/2017test&qru=/ta/2017test/question-ranking

解题思路： DP。dp[i][j][0]表示在前i个人里选满足条件的j个人且最后一个人是i的最大值，dp[i][j][1]为对应的最小值。

dp[i][j][0] = max(dp[i-k][j-1][l] * a[i]) 其中k = 1,2，..., D, 和 l = 0,1。dp[i][j][1]有类似的转移方程。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int imax_n = 55;
 5 
 6 int a[imax_n];
 7 long long dp[imax_n][15][2];
 8 int n;
 9 int K;
10 int D;
11 
12 int main()
13 {
14     while (scanf("%d", &n)!=-1)
15     {
16         memset(dp, 0, sizeof(dp));
17         for (int i = 1; i <= n; ++i)
18         {
19             scanf("%d", &a[i]);
20         }
21         scanf("%d%d", &K, &D);
22         dp[0][0][0] = dp[0][0][1] = 1LL;
23         for (int i = 1; i <= n; ++i)
24         {
25             dp[i][0][0] = 1LL;
26             dp[i][0][1] = 1LL;
27             for (int j = 1; j <= K && j <= i; ++j)
28             {
29                 for (int k = 1; k <= D && i >= k; ++k)
30                 {
31                     for (int l = 0; l <= 1; ++l)
32                     {
33                         dp[i][j][0] = max(dp[i][j][0], dp[i-k][j-1][l] * a[i]);
34                         dp[i][j][1] = min(dp[i][j][1], dp[i-k][j-1][l] * a[i]);
35                     }
36                 }
37             }
38         }
39         long long ans = 0;
40         for (int i = 1; i <= n; ++i)
41         {
42             ans = max(ans, dp[i][K][0]);
43         }
44         printf("%lld
", ans);
45     }
46     return 0;
47 }