【 Educational Codeforces Round 93 (Rated for Div. 2) D】Colored Rectangles
for Codeforces div round 93 Educational Rated
2023-09-14 09:03:41 时间
题目链接
翻译
题目描述挺绕的。
有 \(3\) 种颜色的棍子吧。
每种颜色棍子提供的时候都是一对一对给的(也即两根两根地给,然后颜色相同,长度也相同)。
每种颜色有 \(limited\) 对不同长度棍子。
然后题目的意思是说选两种不同颜色,然后分别选一对棍子。(这样就有 \(4\) 根棍子了)
组成矩形,相同颜色的在对边(长度相同所以都在对边)。
问你这些棍子组成的矩形和的最大值是多少。
题解
肯定贪心地选择长的棍子(这样有剩下的话,剩下的也是短棍子),长棍子更容易组成面积更大的矩形嘛。
然后 \(N\) 这么小,就很明显是一个 \(DP\) 了。
设 \(f[i][j][k]\) 表示红色剩 \(i\) 对, 绿色剩 \(j\) 对, 黑色剩 \(k\) 对能组成的最大面积值。
初始值的话就全 \(0\) 就好。但实际上是 \(f[i][0][0],f[0][j][0],f[0][0][k]\) 这些为 \(0\),这些状态没办法组成两堆了。
状态转移方程就类似 \(f[i][j][k] = max(f[i][j][k],f[i-1][j-1][k]+r[i]*g[j])\) 这样。
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 200;
int R,G,B;
int r[N + 10],g[N + 10],b[N + 10];
LL f[N + 10][N + 10][N + 10];
bool cmp(int a,int b){
return a < b;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin >> R >> G >> B;
for (int i = 1;i <= R; i++){
cin >> r[i];
}
sort(r+1,r+1+R,cmp);
for (int i = 1;i <= G; i++){
cin >> g[i];
}
sort(g+1,g+1+G,cmp);
for (int i = 1;i <= B; i++){
cin >> b[i];
}
sort(b+1,b+1+B,cmp);
LL ans = 0;
for (int i = 0;i <= R; i++){
for (int j = 0;j <= G; j++){
for (int k = 0; k <= B; k++){
if (i > 0 && j > 0){
f[i][j][k] = max(f[i][j][k],f[i-1][j-1][k] + r[i]*g[j]);
}
if (i > 0 && k > 0){
f[i][j][k] = max(f[i][j][k],f[i-1][j][k-1] + r[i]*b[k]);
}
if (j > 0 && k > 0){
f[i][j][k] = max(f[i][j][k],f[i][j-1][k-1] + g[j]*b[k]);
}
ans = max(ans,f[i][j][k]);
}
}
}
cout << ans << endl;
return 0;
}
相关文章
- burpsuite for Mac安装激活
- [Angular] Standalone component - routes top level provide share for all child routes
- [Angular 9 Unit testing] Stronger typing for dependency injection in tests
- [Angular2 Form] Validation message for Reactive form
- mysql中You can’t specify target table for update in FROM clause错误解决方法
- [SCSS] Write similar classes with the SCSS @for Control Directive
- [Webpack 2] Hashing with Webpack for long term caching
- 【Codeforces Round #693 (Div. 3) A】Cards for Friends
- 【Educational Codeforces Round 97 (Rated for Div. 2) C】Chef Monocarp
- 【Educational Codeforces Round 81 (Rated for Div. 2) C】Obtain The String
- 【Educational Codeforces Round 48 (Rated for Div. 2) C】 Vasya And The Mushrooms
- 【Educational Codeforces Round 41 (Rated for Div. 2) D】Pair Of Lines
- 【Educational Codeforces Round 33 A】Chess For Three
- 成功解决ValueError: Input contains NaN, infinity or a value too large for dtype('float64').
- 嵌入式linux开发,交叉编译qt4.8.5报错:Makefile:1054: recipe for target ‘.moc/release-shared-emb-arm/moc_qabstract