h5做的分销网站,可以自己设计装修的免费软件,中国做机床的公司网站,做网站的是什么软件题目描述#xff1a; 分析#xff1a;
乍一看我还以为是贪心#xff01; 猫 想想感觉没问题 但是局部最优并不能保证全局最优 比如这组数据
19 19 19 19
20 20
20 20如果按照贪心的做法#xff0c;答案是20*20*2 但是其实答案是19*20*4
因此这道题用贪心是不对的
于是我…题目描述 分析
乍一看我还以为是贪心 猫 想想感觉没问题 但是局部最优并不能保证全局最优 比如这组数据
19 19 19 19
20 20
20 20如果按照贪心的做法答案是20*20*2 但是其实答案是19*20*4
因此这道题用贪心是不对的
于是我们考虑dp 可以观察到这道题的n非常小只有200 这就暗示我们这道题可以用 n 3 n^3 n3的做法去解决
那么我们就可以这样设dp状态 f [ i ] [ j ] [ k ] 表示用三个颜色分别用了前 i , j , k 个数所能获得的最大价值 f[i][j][k]表示用三个颜色分别用了前i,j,k个数所能获得的最大价值 f[i][j][k]表示用三个颜色分别用了前i,j,k个数所能获得的最大价值 如何转移呢 考虑一次可以取两个数 也就是说可以取12,23,13 那么分别从这三种状态转移过来即可
有的时候记忆化搜索比dp更好写 Code
#includebits/stdc.h
using namespace std;const int N 210;
int r,g,bb;
int a[N],b[N],c[N];
int f[N][N][N];bool cmp(int x,int y){return xy;
}int Dfs(int x,int y,int z){if (f[x][y][z]) return f[x][y][z];int Max 0;if (x y) Max max(Max,Dfs(x-1,y-1,z)a[x]*b[y]);if (x z) Max max(Max,Dfs(x-1,y,z-1)a[x]*c[z]);if (z y) Max max(Max,Dfs(x,y-1,z-1)b[y]*c[z]);return f[x][y][z] Max;
}int main(){cinrgbb;for (int i 1; i r; i) cina[i];for (int i 1; i g; i) cinb[i];for (int i 1; i bb; i) cinc[i];sort(a1,ar1);sort(b1,bg1);sort(c1,cbb1);coutDfs(r,g,bb)endl;return 0;
}
