算法1
(dp) $O(tnm)$
Luogu5662纪念品
题面https://www.luogu.com.cn/problem/P5662
这道题没什么细节
是dp
考虑T=1时
显然一天无论怎么买怎么卖最后的值还是m,输出m
t=2很关键
两天时是完全背包
总体积是m,因为第一天买花费钱数必须不能超过m
单体积为第一天的价格
单价值为第二天-第一天价格,显然当有物品的单价值<0时意味着买卖这个物品会赔钱,所以跳过这个物品,不参与dp
而每个物品可以买无限个
所以是完全背包而非01背包
进行完全背包
最后dp[m]为最大利润
输出m+dp【m】
推广到一般情况
当第i天买第k天卖
由于每天可以无限次买卖
所以相当于第i天买第i+1天卖第i+1天再买,第i+2天再卖
所以2天2天的完全背包
把每次完全背包后的利润加在一起
m也要随之更新
每一次完全背包m都要加上这次的利润
最后输出和
注意:!!dp数组的大小不是纪念品的个数而是总体积大小,所以开到10^4而非100,在这里wa了一次
时间复杂度
完全背包优化后为$O(nm)$
n是物品个数,m是体积(这里m为金币数)
执行t-1次
所以为$O(tnm)$
C++ 代码
#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
using namespace std;
int dp[10009],a[103][103];
using namespace std;
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>>a[i][j];
}
}
//int tot=0;
for(int i=1;i<=t-1;++i){
memset(dp,0,sizeof dp);
int v=m;
for(int j=1;j<=n;++j){
int vi=a[i][j];
int wi=a[i+1][j]-a[i][j];
if(wi<=0)continue;
for(int z=vi;z<=v;++z){
dp[z]=max(dp[z],dp[z-vi]+wi);
}
}
m=m+dp[v];
}
cout<<m<<endl;
return 0;
}