您当前的位置: 首页 > 

对方正在debug

暂无认证

  • 5浏览

    0关注

    399博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

Colored Rectangles(贪心/dp)

对方正在debug 发布时间:2020-08-16 14:23:24 ,浏览量:5

题目 题意:给定 r e d , g r e e n , b l u e red,green,blue red,green,blue三种颜色的板子,数量分别有 r , g , b r,g,b r,g,b对,长度为 r i , g j , b k r_i,g_j,b_k ri​,gj​,bk​。用两种颜色组成一个长方形,问能组成的最大面积。

思路:贪心,大的长度和大的长度匹配,这样可以最优。预处理排序,定义 d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k]表示取前 i , j , k i,j,k i,j,k个木板,能组成的最大面积,答案为 d p [ r ] [ g ] [ b ] dp[r][g][b] dp[r][g][b]。dp转移方程比较显然。

#include
#include
#include
#include
#include
using namespace std;
#define ll long long
const int maxn = 205;

int nr, ng, nb;
int r[maxn], g[maxn], b[maxn];
ll dp[maxn][maxn][maxn];

bool cmp(const ll &x, const ll &y) {
    return x             
关注
打赏
1664895754
查看更多评论
0.0414s