首页 > 代码库 > HDU -2670 Girl Love Value
HDU -2670 Girl Love Value
这道题是刚好装满的背包问题，刚好选取k个，状态转移方程为dp[i][j] = max( dp[i - 1][j], dp[i - 1][j - 1] + Li - Bi(j - 1) )
dp[i][j] 表示从前 i 个男孩中选取 j 个的 Li 的最大值， 首先按照Bi 排一下序，这个是利用贪心的思想，因为那样才能获得最优解，按照递减排序，这样才能找到最大值，然后就是dp了，状态转移方程的意思就是第 j 个去或者不 取，代码如下
代码一(二维数组版)：
1 #include <stdio.h> 2 #include <iostream> 3 #include <string.h> 4 #include <algorithm> 5 using namespace std; 6 struct Happy{ 7 int Li, Bi; 8 }; 9 const int N = 1002;10 int dp[N][N]; 11 Happy happy[N];12 bool cmp(Happy a, Happy b)//递减排序 13 {14 return a.Bi > b.Bi;15 }16 int main()17 {18 int n, v;19 while (~scanf("%d %d", &n, &v))20 {21 memset(dp, 0, sizeof(dp)); 22 for (int i = 1; i <= n; i++)23 scanf("%d", &happy[i].Li);24 for (int i = 1; i <= n; i++)25 scanf("%d", &happy[i].Bi);26 sort(happy + 1, happy + n + 1, cmp);//贪心思想 27 for (int i = 1; i <= n; i++)28 {29 for (int j = 1; j <= i && j <= v; j++)30 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + happy[i].Li - happy[i].Bi * (j - 1));31 }32 printf("%d\n", dp[n][v]);33 }34 35 return 0;36 }
代码二(优化空间版)：
1 #include <stdio.h> 2 #include <iostream> 3 #include <string.h> 4 #include <algorithm> 5 using namespace std; 6 struct Happy{ 7 int Li, Bi; 8 }; 9 const int N = 10002;10 int dp[N]; 11 Happy happy[N];12 bool cmp(Happy a, Happy b)//递减排序 13 {14 return a.Bi > b.Bi;15 }16 int main()17 {18 int n, v;19 while (~scanf("%d %d", &n, &v))20 {21 memset(dp, 0, sizeof(dp)); 22 for (int i = 1; i <= n; i++)23 scanf("%d", &happy[i].Li);24 for (int i = 1; i <= n; i++)25 scanf("%d", &happy[i].Bi);26 sort(happy + 1, happy + n + 1, cmp);//贪心思想 27 for (int i = 1; i <= n; i++)28 {29 for (int j = v; j >= 1; j--)30 /*这句话等价于dp[j] = max(dp[j], dp[j - 1] + happy[i].Li - happy[i].Bi * (j - 1))，只不过用if更快*/ 31 if (dp[j - 1] + happy[i].Li - happy[i].Bi * (j - 1 ) > dp[j])32 dp[j] = dp[j - 1] + happy[i].Li - happy[i].Bi * (j - 1 );33 }34 printf("%d\n", dp[v]);35 }36 37 return 0;38 }
HDU -2670 Girl Love Value
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。