首页 » 未分类 » 正文

2019普及组第3题 纪念品

动态规划:
dp[i]为第i天结束后最多有多少钱,第0天结束我们可以知道是m元。

dp[5] – dp[0] = dp[5] – dp[4] + dp[4] – dp[3] + dp[3] – dp[2] + dp[2] – dp[1] + dp[1] – dp[0]
dp[5] – dp[0] =(dp[5]-dp[4])+(dp[4]-dp[3])+(dp[3] – dp[2])+(dp[2] – dp[1])+(dp[1] – dp[0])

所以第5天和第0天的钱的差值 就是 所有第a天买入,第a+1天卖出的收益的和。
因此我们只需要考虑使a天买入,a+1天卖出赚的最多即可。而每天的背包容量则为当天的m,便成为了一个完全背包问题。

#include<bits/stdc++.h>

using namespace std; 

int price[101][101];  

const int maxm = 1e4+5;  

int dp[maxm];  //dp[i]是有m块钱最多在第二天赚多少 

int main(){
    int t, n, m;  
    cin >> t >> n >> m;  
    for(int i=1; i<=t; i++){
        for(int j=1; j<=n; j++){
            cin >> price[i][j];  
        }
    } 

    //可以在1到(t-1)天进行购买 
    for(int i=1; i<t; i++){ 
        memset(dp, 0, sizeof(dp));   
        //纪念品 
        for(int j=1; j<=n; j++){
            //枚举钱,从price[i][j]开始,只有钱不少于price[i][j]才能买第j件物品 
            for(int k=price[i][j]; k<=m; k++){
                dp[k]=max(dp[k], dp[k-price[i][j]]+price[i+1][j]-price[i][j]);  
            }
        }
        //这里m只要加上dp[m]就可以了 
        m += dp[m];  
    }

    cout << m<<endl;  
    return 0;  
} 

发表评论