洛谷P2392 背包问题
题目链接: 传送门
看完题目就感觉是个贪心,样例也能推过去,于是交了以下代码:
/*
* @Author: hesorchen
* @Date: 2020-04-14 10:33:26
* @LastEditTime: 2020-05-13 14:29:51
* @Link: https://hesorchen.github.io/
*/
#include <map>
#include <set>
#include <list>
#include <queue>
#include <deque>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define endl '\n'
#define PI cos(-1)
#define PB push_back
#define ll long long
#define INF 0x3f3f3f3f
#define mod 1000000009
#define lowbit(abcd) (abcd & (-abcd))
#define fre \
{ \
freopen("in.txt", "r", stdin); \
freopen("out.txt", "w", stdout); \
}
ll a1[50];
ll a2[50];
ll a3[50];
ll a4[50];
int main()
{
ll s1, s2, s3, s4;
cin >> s1 >> s2 >> s3 >> s4;
for (int i = 1; i <= s1; i++)
cin >> a1[i];
for (int i = 1; i <= s2; i++)
cin >> a2[i];
for (int i = 1; i <= s3; i++)
cin >> a3[i];
for (int i = 1; i <= s4; i++)
cin >> a4[i];
ll ans = 0;
sort(a1 + 1, a1 + 1 + s1, greater<int>());
sort(a2 + 1, a2 + 1 + s2, greater<int>());
sort(a3 + 1, a3 + 1 + s3, greater<int>());
sort(a4 + 1, a4 + 1 + s4, greater<int>());
ll pos;
ll l, r;
l = 1, r = 2;
while (l <= s1)
{
if (a1[l] > 0 && a1[r] > 0)
a1[l]--, a1[r]--;
else if (a1[l] > 0)
a1[l]--;
ans++;
if (a1[r] == 0 && a1[l] == 0)
l += 2, r += 2;
else if (a1[r] == 0)
r += 1;
else if (a1[l] == 0)
l += 1, r += 1;
}
l = 1, r = 2;
while (l <= s2)
{
if (a2[l] > 0 && a2[r] > 0)
a2[l]--, a2[r]--;
else if (a2[l] > 0)
a2[l]--;
ans++;
if (a2[r] == 0 && a2[l] == 0)
l += 2, r += 2;
else if (a2[r] == 0)
r += 1;
else if (a2[l] == 0)
l += 1, r += 1;
}
l = 1, r = 2;
while (l <= s3)
{
if (a3[l] > 0 && a3[r] > 0)
a3[l]--, a3[r]--;
else if (a3[l] > 0)
a3[l]--;
ans++;
if (a3[r] == 0 && a3[l] == 0)
l += 2, r += 2;
else if (a3[r] == 0)
r += 1;
else if (a3[l] == 0)
l += 1, r += 1;
}
l = 1, r = 2;
while (l <= s4)
{
if (a4[l] > 0 && a4[r] > 0)
a4[l]--, a4[r]--;
else if (a4[l] > 0)
a4[l]--;
ans++;
if (a4[r] == 0 && a4[l] == 0)
l += 2, r += 2;
else if (a4[r] == 0)
r += 1;
else if (a4[l] == 0)
l += 1, r += 1;
}
cout << ans << endl;
return 0;
}
结果一个测试点都没过。看了一下题解,发现很多人都以为是贪心,果然没有经过系统证明的猜想都是耍流氓
解题思路:我们可以将每一门课的复习点分成两组,并且保证两组的差值尽可能小,那么就可以转换成01背包问题,背包的最大容量为 s u m 2 \frac{sum}{2} 2sum,求出背包最多能装多少物品。结果就是 s u m − s u m 2 sum-\frac{sum}{2} sum−2sum
AC代码:
/*
* @Author: hesorchen
* @Date: 2020-04-14 10:33:26
* @LastEditTime: 2020-05-13 14:57:12
* @Link: https://hesorchen.github.io/
*/
#include <map>
#include <set>
#include <list>
#include <queue>
#include <deque>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define endl '\n'
#define PI cos(-1)
#define PB push_back
#define ll long long
#define INF 0x3f3f3f3f
#define mod 1000000009
#define lowbit(abcd) (abcd & (-abcd))
#define fre \
{ \
freopen("in.txt", "r", stdin); \
freopen("out.txt", "w", stdout); \
}
ll a1[50];
ll a2[50];
ll a3[50];
ll a4[50];
ll dp[500000];
int main()
{
ll s1, s2, s3, s4;
cin >> s1 >> s2 >> s3 >> s4;
for (int i = 1; i <= s1; i++)
cin >> a1[i];
for (int i = 1; i <= s2; i++)
cin >> a2[i];
for (int i = 1; i <= s3; i++)
cin >> a3[i];
for (int i = 1; i <= s4; i++)
cin >> a4[i];
ll ans = 0;
ll sum, sum_2;
fill(dp, dp + 600, 0);
sum = 0;
for (int i = 1; i <= s1; i++)
sum += a1[i];
sum_2 = sum;
sum = sum / 2;
for (int i = 1; i <= s1; i++)
for (int j = sum; j >= 0; j--)
if (j >= a1[i])
dp[j] = max(dp[j], dp[j - a1[i]] + a1[i]);
ans += sum_2 - dp[sum];
fill(dp, dp + 600, 0);
sum = 0;
for (int i = 1; i <= s2; i++)
sum += a2[i];
sum_2 = sum;
sum = sum / 2;
for (int i = 1; i <= s2; i++)
for (int j = sum; j >= 0; j--)
if (j >= a2[i])
dp[j] = max(dp[j], dp[j - a2[i]] + a2[i]);
ans += sum_2 - dp[sum];
fill(dp, dp + 600, 0);
sum = 0;
for (int i = 1; i <= s3; i++)
sum += a3[i];
sum_2 = sum;
sum = sum / 2;
for (int i = 1; i <= s3; i++)
for (int j = sum; j >= 0; j--)
if (j >= a3[i])
dp[j] = max(dp[j], dp[j - a3[i]] + a3[i]);
ans += sum_2 - dp[sum];
fill(dp, dp + 600, 0);
sum = 0;
for (int i = 1; i <= s4; i++)
sum += a4[i];
sum_2 = sum;
sum = sum / 2;
for (int i = 1; i <= s4; i++)
for (int j = sum; j >= 0; j--)
if (j >= a4[i])
dp[j] = max(dp[j], dp[j - a4[i]] + a4[i]);
ans += sum_2 - dp[sum];
cout << ans << endl;
return 0;
}
更多推荐
所有评论(0)