程序员自己做网站怎么赚钱,青海网站建设费用价格,住房和城乡建设部网站 绿地,凤岗网站建设题意#xff1a;有背包容量为c 给出两个数串 表示两种不同的物品 从物品中任意选多个数
价值是背包剩余空间*选择元素所属数串的系数
问 最大价值分析: 表面上看起来是个背包题 但是空间太大导致不能背
这里发现先放空间小的换来的价值大 所以我们应该先把两个数串排序 然后…题意有背包容量为c 给出两个数串 表示两种不同的物品 从物品中任意选多个数
价值是背包剩余空间*选择元素所属数串的系数
问 最大价值分析: 表面上看起来是个背包题 但是空间太大导致不能背
这里发现先放空间小的换来的价值大 所以我们应该先把两个数串排序 然后枚举
这里由于要考虑次序的问题 于是先放哪个 就需要用动态规划的思路 选择价值更大的
dp[i][j] 表示总要选择第一个类型中前i个数 和第二个类型中j个数 那么这个结果最大的可能就是
max(dp[i][j-1]第j个物品最后放进去的价值dp[i-1][j]第i个物品放进去的价值)code注意如果把dp数组全 memset 会超时 循环初始化才会没问题 后来用java写超时 用c写过了 。。。 无语的java
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int maxn 2010;
ll sum1[maxn],sum2[maxn],dp[maxn][maxn];
int a[maxn],b[maxn];
int main() {int t;scanf(%d,t);while(t--) {int n,m,c;int k1,k2;sum1[0] sum2[0] 0;a[0] b[0] 0;ll ans-1;scanf(%d%d%d%d%d,k1,k2,c,n,m);for(int i0;in;i) {for(int j0;jm;j)dp[i][j] 0;}for(int i1;in;i) {scanf(%d,a[i]); }for(int i1;im;i) {scanf(%d,b[i]);}sort(a1,a1n);sort(b1,b1m);for(int i1;in;i) {sum1[i] sum1[i-1] a[i];}for(int i1;im;i) {sum2[i] sum2[i-1] b[i];}for(int i1;in;i) {ll s sum1[i];if(cs) {dp[i][0] dp[i-1][0] k1*(c-s);ans max(dp[i][0],ans);}}for(int j1;jm;j) {ll s sum2[j];if(cs) {dp[0][j] dp[0][j-1] k2*(c-s);ans max(dp[0][j],ans);}}for(int i1;in;i) {for(int j1;jm;j) {ll s sum1[i] sum2[j];if(cs) {dp[i][j] max(dp[i-1][j] k1*(c-s), dp[i][j-1] k2*(c-s));ans max(dp[i][j], ans);}}}printf(%lld\n,ans);}}
