参考:
我背包真是好不熟练啊…… 第一天买了第三天卖相当于第一天买了第二天卖第二天再买第三天再卖。所以问题转化成完全背包,每天转移即可#include#include #include #include using namespace std;const int N=55;int s,d,m,f[5000005],a[N][N];int main(){ scanf("%d%d%d",&s,&d,&m); for(int i=1;i<=s;i++) for(int j=1;j<=d;j++) scanf("%d",&a[i][j]); int ans=m; for(int i=1;i<=d-1;i++) { memset(f,0,sizeof(f)); for(int j=1;j<=s;j++) for(int k=a[j][i];k<=ans;k++) f[k]=max(f[k],f[k-a[j][i]]+a[j][i+1]-a[j][i]); ans+=f[ans]; } printf("%d\n",ans); return 0;}