miemieQWQ @ 2017-12-27 19:53:10
#include <bits/stdc++.h>
using namespace std;
const long long N = 102400, oo = 0x7fffffffffffffffll, p = 0;
long long dp[N] = {0};
long long T, n, a[N], b[N], c[N];
inline bool Comp(const int &x, const int &y)
{
long long tx = (a[x] - (p + c[x]) * b[x]) + (a[y] - (p + c[x] + c[y]) * b[y]);
long long ty = (a[y] - (p + c[y]) * b[y]) + (a[x] - (p + c[x] + c[y]) * b[x]);
return tx < ty;
// return c[x] * b[y] < c[y] * b[x];
}
int main()
{
srand((unsigned)time(NULL));
scanf("%lld%lld", &T, &n);
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
for (int i = 1; i <= n; i++) scanf("%lld", &b[i]);
for (int i = 1; i <= n; i++) scanf("%lld", &c[i]);
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
if (!Comp(i, j))
swap(a[i], a[j]), swap(b[i], b[j]), swap(c[i], c[j]);
long long ans = -oo;
for (int i = 1; i <= n; i++)
for (int j = T; j >= c[i]; j--)
{
dp[j] = max(dp[j],
dp[j-c[i]] + (a[i] - j * b[i]));
ans = max(ans, dp[j]);
}
printf("%lld\n", ans);
return 0;
}
比较函数里注释掉的是对的,没注释掉的是没有化简的式子
我开始不想化简,把这个事情交给程序解决,它就出各种问题, WA飞了
by miemieQWQ @ 2017-12-27 19:54:31
p应该是可以消掉的, 取什么值都没影响吧
by miemieQWQ @ 2017-12-27 20:00:10
好吧,GG,自己解决了
价值大的应该放前面, 符号写反了