传送门
解题思路
本题首先要明白,在每一天时,最优策略是先进行操作2(卖),再进行操作1(买),才能是利益最大化。
本题很显然当只有两天时,是一个完全背包,就是把当日价钱当做体积,把明日价格和今日价格的差作为价值,跑一边完全背包即可。时间复杂度O(TNM)
然后我们考虑满分做法——我们用dp[j]表示还剩下j个体积时,所能获得的最大利益。
然后对于后面的所有天,两天跑一遍完全背包。每一次统计时答案就是dp[m]+m,即利润+本金。
这里一定要注意对于每一天来说,购买的方式对以后的赚钱并未影响,所以只需记录下一天下来最大的钱数(即明日的本金)即可。然后还要清空dp数组。
还有一个重点就是对于每一样物品,在第x天买入k件,第x+1天卖出k件,又买入k件,第x+2天又买入k件,这个过程其实就相当于在第x天买入k件,在x+2天卖出k件,所以我们枚举所有的可能不受限制(只不过多算了几步罢了)。
这里还可以这样理解(贪心):就是在当天买的物品,第二天必须全部卖出去。如果不卖是划算的,那么再买回来即可。
还有一个地方比较难理解:为什么我们不用记录怎样买的呢?在第x天时不会卖出去一些手上没有的纪念品吗?
答案时否定的。Why?
看代码,当我们买某件纪念品的时候,我们加上的价值是(明日价格-今日价格),从数值上讲是加上明天接着卖出的话赚的利润,感性理解的话是今天买的这几件物品在第二天一定全部卖出去。所以每天的操作实际上只有1操作(买)。
很显然,只要钱足够,可以买进无限个。
AC代码
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 using namespace std; 6 const int maxn=105; 7 const int maxm=10005; 8 int T,n,m,p[maxn][maxn],dp[maxm]; 9 //第t天买到第i件物品时剩余容量是j元的最大利润。 10 int main() 11 { 12 cin>>T>>n>>m; 13 for(int i=1;i<=T;i++){ 14 for(int j=1;j<=n;j++) { 15 scanf("%d",&p[i][j]); 16 } 17 } 18 for(int t=1;t<=T;t++){ 19 memset(dp,0,sizeof(dp)); 20 for(int i=1;i<=n;i++){ 21 for(int j=p[t][i];j<=m;j++){ 22 dp[j]=max(dp[j],dp[j-p[t][i]]+p[t+1][i]-p[t][i]); 23 } 24 } 25 m=max(m,dp[m]+m); 26 } 27 cout<<m; 28 return 0; 29 }
//CSP2019普及组 t3