HDU -2670 Girl Love Value

时间:2022-04-03 13:05:29

这道题是刚好装满的背包问题,刚好选取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 个去或者不 取,代码如下

代码一(二维数组版):

 #include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
struct Happy{
int Li, Bi;
};
const int N = ;
int dp[N][N];
Happy happy[N];
bool cmp(Happy a, Happy b)//递减排序
{
return a.Bi > b.Bi;
}
int main()
{
int n, v;
while (~scanf("%d %d", &n, &v))
{
memset(dp, , sizeof(dp));
for (int i = ; i <= n; i++)
scanf("%d", &happy[i].Li);
for (int i = ; i <= n; i++)
scanf("%d", &happy[i].Bi);
sort(happy + , happy + n + , cmp);//贪心思想
for (int i = ; i <= n; i++)
{
for (int j = ; j <= i && j <= v; j++)
dp[i][j] = max(dp[i - ][j], dp[i - ][j - ] + happy[i].Li - happy[i].Bi * (j - ));
}
printf("%d\n", dp[n][v]);
} return ;
}

代码二(优化空间版):

 #include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
struct Happy{
int Li, Bi;
};
const int N = ;
int dp[N];
Happy happy[N];
bool cmp(Happy a, Happy b)//递减排序
{
return a.Bi > b.Bi;
}
int main()
{
int n, v;
while (~scanf("%d %d", &n, &v))
{
memset(dp, , sizeof(dp));
for (int i = ; i <= n; i++)
scanf("%d", &happy[i].Li);
for (int i = ; i <= n; i++)
scanf("%d", &happy[i].Bi);
sort(happy + , happy + n + , cmp);//贪心思想
for (int i = ; i <= n; i++)
{
for (int j = v; j >= ; j--)
/*这句话等价于dp[j] = max(dp[j], dp[j - 1] + happy[i].Li - happy[i].Bi * (j - 1)),只不过用if更快*/
if (dp[j - ] + happy[i].Li - happy[i].Bi * (j - ) > dp[j])
dp[j] = dp[j - ] + happy[i].Li - happy[i].Bi * (j - );
}
printf("%d\n", dp[v]);
} return ;
}