题目描述
尽管奶牛天生谨慎，它们仍然在住房抵押信贷市场中大受打击，现在它们准备在股市上碰碰运
气。贝西有内部消息，她知道 S 只股票在今后 D 天内的价格。
假设在一开始，她筹集了 M 元钱，那么她该怎样操作才能赚到最多的钱呢？贝西在每天可以买
卖多只股票，也可以多次买卖同一只股票，交易单位必须是整数，数量不限。举一个牛市的例子。假
设贝西有 10 元本金，股票价格如下：
| 股票 | 今天的价格 | 明天的价格 | 后天的价格 |
| A | 10 | 15 | 15 |
| B | 13 | 11 | 20 |
最赚钱的做法是：今天买入 A 股 1 张，到明天把它卖掉并且买入 B 股 1 张，在后天卖掉 B 股，这样
贝西就有 24 元了。
输入
• 第一行：三个整数 S，D 和 M，2 ≤ S ≤ 50,2 ≤ D ≤ 10,1 ≤ M ≤ 200000
• 第二行到第 S + 1 行：第 i + 1 行有 D 个整数：P i,1 到 P i,D ，表示第 i 种股票在第一天到最后
一天的售价，对所有 1 ≤ j ≤ D，1 ≤ P i,j ≤ 1000
输出
• 单个整数：表示奶牛可以获得的最大钱数，保证这个数不会超过 500000
样例输入
2 3 10 10 15 15 13 11 20
样例输出
24
题解：
股票问题：第i天买第j天卖 相当于 第i天买 第k天卖第k天再买回来 第j天卖
于是我们只处理i和i+1天
看到题发现dp能开的只有钱数这个数组
于是我们想到背包
把第i天的买入费用当作体积，利润（下一天卖出的前-当天买入的前）看作价值 S看作背包体积进行背包
然后选出最大的利润加到S里面去 表示到当天位置最大的利润 无后效性
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int N=500005; 7 int gi(){ 8 int str=0;char ch=getchar(); 9 while(ch>'9' || ch<'0')ch=getchar(); 10 while(ch>='0' && ch<='9')str=str*10+ch-48,ch=getchar(); 11 return str; 12 } 13 int w[55][15],f[N]; 14 int main() 15 { 16 int n=gi(),m=gi(),S=gi(),tmp; 17 for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)w[i][j]=gi(); 18 for(int i=1;i<m;i++) 19 { 20 memset(f,0,sizeof(f)); 21 for(int j=1;j<=n;j++) 22 { 23 for(int k=w[j][i];k<=S;k++) 24 { 25 tmp=f[k-w[j][i]]+w[j][i+1]-w[j][i]; 26 if(tmp>f[k])f[k]=tmp; 27 } 28 } 29 S+=f[S]; 30 } 31 printf("%d",S); 32 return 0; 33 }