30求调

zhouhaoyu1011 @ 2024-10-09 19:32:38

#include <bits/stdc++.h>
using namespace std;
long long T;
long long n;
struct food{
    long long a;
    long long b;
    long long c;
    long long key;
}eat[60];
long long f[100005];
bool cmp(food a,food b){
    return a.key<b.key;
}
int main(){
    cin>>T>>n;
    for(long long i=1;i<=n;i++){
        cin>>eat[i].a;
    }
    for(long long i=1;i<=n;i++){
        cin>>eat[i].b;
    }
    for(long long i=1;i<=n;i++){
        cin>>eat[i].c;
    }
    for(long long i=1;i<=n;i++){
        eat[i].key=eat[i].b*eat[i].c;
    }

    //f[i][j]   前i件，时间不超过j的最大美味指数
    //f[i][j]=max(f[i-1][j],f[i-1][j-eat[i].c]+eat[i].a-j*eat[i].b);
    long long ans=0;
    sort(eat+1,eat+n+1,cmp);
    for(long long i=1;i<=n;i++){
        for(long long j=T;j>=0;j--){
            if(j-eat[i].c>=0){
                f[j]=max(f[j],f[j-eat[i].c]+eat[i].a-j*eat[i].b);
            }
            ans=max(ans,f[j]);
        }
    }
    for(int i=1;i<=n;i++){

    }
    cout<<ans;
    return 0;
}

by HYLW @ 2024-10-17 21:10:18

式子推错了。

设当前时间为 t ，则对于先后加入两个食材 i,j 来讲，新增美味若满足

不当把 c_i\cdot b_i 当作 key 值比较

by zhouhaoyu1011 @ 2024-10-22 20:56:01

@HYLW 谢谢大佬Orz 我悟了

by lly66666 @ 2024-11-02 10:14:30

@zhouhaoyu1011

补个代码：

#include <bits/stdc++.h>
using namespace std;
long long f[100005], T, n;
struct node{
    long long a1, b1, c1;
}a[100005];
bool cmp(node x, node y) {
    return x.c1 * y.b1 < y.c1 * x.b1;
}
int main() {
    cin >> T >> n;
    for(long long i = 1; i <= n; i ++) {
        cin >> a[i].a1;
    }
    for(long long i = 1; i <= n; i ++) {
        cin >> a[i].b1;
    }
    for(long long i = 1; i <= n; i ++) {
        cin >> a[i].c1;
    }
    sort(a + 1, a + n + 1, cmp);
    for(long long i = 1; i <= n; i ++) {
        for(long long j = T; j >= a[i].c1; j --) {
            f[j] = max(f[j], f[j - a[i].c1] + a[i].a1 - j * a[i].b1);
        }
    }
    long long ans = 0;
    for (long long i = 0; i <= T; i++)
        ans = max(ans, f[i]);
    cout << ans;
    return 0;
}

by zhouhaoyu1011 @ 2024-11-10 09:28:11

thx,过了