2020-2021:teams:too_low:cfedu93_hj

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:too_low:cfedu93_hj [2020/08/21 17:40]
jim 创建
+++ 2020-2021:teams:too_low:cfedu93_hj [2020/08/21 17:53] (当前版本)
jim
@@ 行 31: / 行 31: @@
 ===== B.  Substring Removal Game=====
-**题意：**
-**思路：**
 <hidden>
 <code cpp>
@@ 行 128: / 行 124: @@
 </hidden>
-===== D. Bad Triangle=====
+===== D. Colored Rectangles=====
-**题意：**略
-**思路：**dp
+**思路：**dp，dp[i][j][k]表示r用前i个、g用前j个，b用前k个组成的长方形面积最大值，考虑r、g长方形增设的情况，可由i-1 j-1 k的结果加上剩下r、g边最大值相乘得到。
 <hidden>
 <code cpp>
+#include <bits/stdc++.h>
+using namespace std;
+typedef long long ll;
+const int maxn = 220;
+int r[maxn], g[maxn], b[maxn];
+ll dp[maxn][maxn][maxn];
+int main() {
+    int R, G, B;
+    scanf("%d%d%d", &R, &G, &B);
+    for (int i = 0; i < R; i++) scanf("%d", &r[i]);
+    for (int i = 0; i < G; i++) scanf("%d", &g[i]);
+    for (int i = 0; i < B; i++) scanf("%d", &b[i]);
+    sort(r, r + R, greater<int>());
+    sort(g, g + G, greater<int>());
+    sort(b, b + B, greater<int>());
+    ll ans = -1;
+    for (int i = 0; i <= R; i++)
+        for (int j = 0; j <= G; j++)
+            for (int k = 0; k <= B; k++) {
+                dp[i + 1][j + 1][k] = max(dp[i + 1][j + 1][k], dp[i][j][k] + 1ll * r[i] * g[j]);
+                dp[i + 1][j][k + 1] = max(dp[i + 1][j][k + 1], dp[i][j][k] + 1ll * r[i] * b[k]);
+                dp[i][j + 1][k + 1] = max(dp[i][j + 1][k + 1], dp[i][j][k] + 1ll * g[j] * b[k]);
+                ans = max({ans, dp[i + 1][j + 1][k], dp[i + 1][j][k + 1], dp[i][j + 1][k + 1]});
+            }
+    printf("%lld\n", ans);
+    return 0;
+}
 </code>
 </hidden>

2020-2021/teams/too_low/cfedu93_hj.1598002817.txt.gz · 最后更改: 2020/08/21 17:40 由 jim