【BZOJ】1578: [Usaco2009 Feb]Stock Market 股票市场

【题意】给定s个股票和d天，给出价格矩阵s*d，每天可以买入或卖出整数倍股票，初始资金m，求最大利益。m<=200000,s<=50,d<=10。

【算法】完全背包

【题解】关键在于转化：第一天买入-第三天卖出，相当于，第一天买入-第二天卖出-第二天买入-第三天卖出。那么买卖股票就变成相邻两天的事情了。

对于每一天，就是完全背包，总重量为资金，重量为当天价格，价值为第二天价格-当天价格。

f[i][j]表示前i个股票使用资金j能获得的最大收益。

f[i][j]=f[i-1][j-A[i]]+A[i+1]-A[i]。

每天最终得到的最大收益就是当天买入第二天卖出后的净收益，加入资金中。如此做d-1次完全背包，得到答案。

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int maxn=;

int n,m,d,f[maxn],a[][];

int main(){

    scanf("%d%d%d",&n,&d,&m);

    for(int i=;i<=n;i++)for(int j=;j<=d;j++)scanf("%d",&a[j][i]);

    for(int k=;k<d;k++){

        memset(f,,sizeof(f));

        for(int i=;i<=n;i++)

            for(int j=a[k][i];j<=m;j++)

                f[j]=max(f[j],f[j-a[k][i]]+a[k+][i]-a[k][i]);

        m+=f[m];

    }

    printf("%d",m);

    return ;

}

巴特西

【BZOJ】1578: [Usaco2009 Feb]Stock Market 股票市场

最新文章

热门文章