正題

題目鏈接:https://www.luogu.com.cn/problem/P5662

---

題目大意

有$T$天，$n$個紀念品，每個紀念品每天的價格不同，數量不限。開始小明有$m$塊錢，求最后一天的最多錢。

---

解題思路

因為一個紀念品可以一天賣出并且一天買入，所以我們固定每個買下來的物品第二天一定賣出，那么我們可以設$f_k$表示到第$i$天剩余價錢為$k$時明天最多可以賺到多少錢，然后就是一個很簡單的$dp$了。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int t,n,m,p[110][11000],f[21000],ans; int main() {scanf("%d%d%d",&t,&n,&m);for(int i=1;i<=t;i++)for(int j=1;j<=n;j++)scanf("%d",&p[j][i]);ans=m;for(int i=1;i<t;i++){memset(f,0xcf,sizeof(f));f[ans]=ans;for(int j=1;j<=n;j++)for(int k=ans-p[j][i];k>=0;k--){f[k]=max(f[k],f[k+p[j][i]]+p[j][i+1]-p[j][i]);ans=max(ans,f[k]);}}printf("%d",ans); }

總結

以上是生活随笔為你收集整理的P5662-纪念品【dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。