蒟蒻求助
查看原帖
蒟蒻求助
547908
NightTide楼主2021/10/20 20:22

RT,第七个点 WA 了,应该不是精度的原因,求助大佬

#include<bits/stdc++.h>
#define MAXN 2010
#define INF 1000000010
using namespace std;
typedef long long ll;
struct kinsen{
    ll price;
    ll max_num;
};
ll n,maxp,w,ans;
kinsen buy[MAXN],sell[MAXN];
ll f[MAXN][MAXN];
void solve(){
    memset(f,-0x3f,sizeof(f));
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=buy[i].max_num;j++){
            f[i][j]=-buy[i].price*j;
        }
    }
    // for(ll i=1;i<=n;i++){
    //     for(ll j=1;j<=maxp;j++){
    //         printf("%lld ",f[i][j]);
    //     }
    //     printf("\n");
    // }
    // printf("\n");
    for(ll i=1;i<=n;i++){
        for(ll j=0;j<=maxp;j++){
            //不买不卖
            f[i][j]=max(f[i][j],f[i-1][j]);
            if(i<=w) continue;
            //在之前的基础上买股票
            if(j>=buy[i].max_num){
                for(ll k=j-buy[i].max_num;k<j;k++){
                    f[i][j]=max(f[i][j],f[i-w-1][k]-(j-k)*buy[i].price);
                }
            }
            //在之前的基础上卖股票
            for(ll k=sell[i].max_num+j;k>j;k--){
                f[i][j]=max(f[i][j],f[i-w-1][k]+(k-j)*sell[i].price);
            }
        }
    }
}
int main(){
    // freopen("trade.in","r",stdin);
    // freopen("trade.out","w",stdout);
    scanf("%lld%lld%lld",&n,&maxp,&w);
    for(ll i=1;i<=n;i++){
        scanf("%lld%lld%lld%lld",&buy[i].price,&sell[i].price,&buy[i].max_num,&sell[i].max_num);
    }
    solve();
    // for(ll i=1;i<=n;i++){
    //     for(ll j=1;j<=maxp;j++){
    //         printf("%lld ",f[i][j]);
    //     }
    //     printf("\n");
    // }
    for(ll i=0;i<=maxp;i++){
        ans=max(ans,f[n][i]);
    }
    printf("%lld\n",ans);
    return 0;
}
2021/10/20 20:22
加载中...