纪念品

Link

基础还是太差，考场上想了巨久最后交的暴力。

核心思想：一个物品可以保存多天，这样无法存状态，所以转换为第一天买入，然后第二天立即卖出，在当天又立即买回，然后第三天又卖出……一直这样，和把一个物品保存 \(n\) 天是等价的，而且还好存状态。至于一个物品保存几天取决于最优决策。

定义 \(dp[i][j][k]\) 表示在第 \(i\) 天，当前考虑到第 \(j\) 个物品，手头有 \(k\) 元钱时最终可以达到的最大收益。那么答案就是 \(max\){\(dp[T][n][k]\)}。

分别考虑买或不买，容易写出方程 $$dp[i][j][k]=max(dp[i][j-1][k],dp[i][j-1][k+v[i][j]]+v[i+1][j]-v[i][j])$$
其中，\(v[i][j]\) 为第 \(i\) 天物品 \(j\) 的价值。

第一维显然可以滚掉，因为转移与天数无关。而每次转移只与前一个物品有关，所以第二维也可以滚掉，倒序枚举即可。

最终的方程为 $$dp[k]=max(dp[k],dp[k+v[i][j]]+v[i+1][j]-v[i][j])$$

Code:

#include<stdio.h>
#include<string.h>
#define N 107

template<class T>
inline void read(T &x){
    x=0;T flag=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')flag*=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
    x*=flag;
}

int T,n,m,v[N][N],dp[N*N];
inline int max(int x,int y){return x>y? x:y;}
int main(){
    read(T),read(n),read(m);
    for(int i=1;i<=T;i++)
        for(int j=1;j<=n;j++)
            read(v[i][j]);
    int ans=m;
    for(int i=1;i<=T;i++){
        memset(dp,0,sizeof(dp));
        dp[ans]=ans;
        for(int j=1;j<=n;j++)
            for(int k=ans;k>=v[i][j];k--)
                dp[k-v[i][j]]=max(dp[k-v[i][j]],dp[k]+v[i+1][j]-v[i][j]);
        int ret=0;
        for(int k=0;k<=ans;k++)
            ret=max(ret,dp[k]);
        ans=ret;
    }
    printf("%d",ans);
}