简答题 偏难
#22106

纪念品

纪念品


未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include&lt;iostream&gt; #include&lt;cstring&gt; using namespace std;   int T,N,M; int dp[10001]; int price[101][10001]; int main(){        cin&gt;&gt;T&gt;&gt;N&gt;&gt;M;        for(int i=1;i&lt;=T;i++){               for(int j=1;j&lt;=N;j++){                      cin&gt;&gt;price[i][j];               }        }        int maxn=0;        for(int i=2;i&lt;=T;i++){               maxn=0;               memset(dp,0,sizeof(dp));               for(int j=1;j&lt;=N;j++){                      for(int k=price[i-1][j];k&lt;=M;k++){                             dp[k]=max(dp[k],dp[k-price[i-1][j]]+price[i][j]-price[i-1][j]);                             maxn=max(maxn,dp[k]);                      }               }               M+=maxn;        }        cout &lt;&lt;M&lt;&lt; endl;          return 0; }</pre><p><br/></p>
解析

如果只有1天的话,买了再卖,总共剩下M个金币。

T天N种纪念币,根据题目设定范围,100以内,可以用二维表格推导。

时间不可逆,只能1~N。

每天买哪些纪念品呢?根据测试样例分析,纪念品任意多,没有个数限制。根据金币的上限,可以推到出这个就是完全背包。大家可以套一下完全背包的算法。每天需要做一次完全背包处理,当天不想卖出金币,相当于卖出金币再买入金币。