问一个很菜的问题,比较函数不化简为什么就错了

P1417 烹调方案

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,自己解决了

价值大的应该放前面, 符号写反了


|