关键词：
可以看出
第一天买，第三天卖 == 第一天买，第二天卖完再买，第三天卖
所以我们只考虑前一天买，后一天卖即可
那么有按天数来划分
f[i][j]表示前i天，共有j元，最大的盈利
第一维可以省去
那么有两种选择，不买 或者 前一天买，后一天卖
#include <cstdio>
#include <cstring>
#include <iostream>
#define N 500001
#define max(x, y) ((x) > (y) ? (x) : (y))
int s, d, m;
int f[N], a[51][51];
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1;
for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘;
return x * f;
}
int main()
{
int i, j, k;
s = read();
d = read();
m = read();
for(i = 1; i <= s; i++)
for(j = 1; j <= d; j++)
a[i][j] = read();
for(i = 2; i <= d; i++)
{
memset(f, 0, sizeof(f));
for(j = 1; j <= s; j++)
for(k = a[j][i - 1]; k <= m; k++)
f[k] = max(f[k], f[k - a[j][i - 1]] + a[j][i] - a[j][i - 1]);
m += f[m];
}
printf("%d
", m);
}
bzoj1578/usaco2009febstockmarket股票市场——完全背包
Description尽管奶牛们天生谨慎，她们仍然在住房抵押信贷市场中受到打击，现在她们开始着手于股市。Bessie很有先见之明，她不仅知道今天S(2<=S<=50)只股票的价格，还知道接下来一共D(2<=D<=10)天的（包括今天）。给定一个... 查看详情
[bzoj1577][usaco2009feb]庙会捷运fairshuttle_贪心_线段树
庙会捷运FairShuttlebzoj-1577Usaco-2009Feb题目大意：有一辆公交车从1走到n。有m群奶牛从$S_i$到$E_i$，第i群奶牛有$W_i$只。车有一个容量c。问不走回头路的情况下最多使多少奶牛到达目的地。其中，每一群奶牛不一定都拉走。注释：$1le... 查看详情
bzoj1579[usaco2009feb]revampingtrails道路升级
1579:[Usaco2009Feb]RevampingTrails道路升级TimeLimit:10SecMemoryLimit:64MBSubmit:2343Solved:666[Submit][Status][Discuss]Description每天,农夫John需要经过一些道路去检查牛棚N里面的牛.农场上有M(1<=M<=50,000)条双向泥土道路,编号为1..M.道路i连接 查看详情
bzoj1579:[usaco2009feb]revampingtrails道路升级dijkstra,堆,分层图
1579:[Usaco2009Feb]RevampingTrails道路升级TimeLimit: 10Sec MemoryLimit: 64MBSubmit: 1573 Solved: 428[Submit][Status][Discuss]Description每天,农夫John需要经过一些道路去检查牛棚N里面的 查看详情
bzoj1579:[usaco2009feb]revampingtrails道路升级
1579:[Usaco2009Feb]RevampingTrails道路升级TimeLimit: 10Sec MemoryLimit: 64MBDescription每天,农夫John需要经过一些道路去检查牛棚N里面的牛.农场上有M(1<=M<=50,000)条双向泥土道路,编号为1..M.道路i连接牛棚P1_i和P2_i(1<=P1_i 查看详情
[bzoj3398][usaco2009feb]bullcow牡牛和牝牛（动态规划）
3398:[Usaco2009Feb]Bullcow牡牛和牝牛TimeLimit: 1Sec MemoryLimit: 128MBSubmit: 235 Solved: 159[Submit][Status][Discuss]Description 约翰要带N(1≤N≤ 查看详情
bzoj1579:[usaco2009feb]revampingtrails道路升级优先队列+dij
1579:[Usaco2009Feb]RevampingTrails道路升级TimeLimit: 10Sec MemoryLimit: 64MBSubmit: 1768 Solved: 481[Submit][Status][Discuss]Description每天,农夫John需要经过一些道路去检查牛棚N里面的 查看详情
bzoj1579[usaco2009feb]revampingtrails道路升级
堆优化的dijkstra。把一个点拆成k个。日常空间要开炸一次。。//Twenty#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>#include<queue>#include<vector>t 查看详情
bzoj15791579:[usaco2009feb]revampingtrails道路升级（最短路）
1579:[Usaco2009Feb]RevampingTrails道路升级Description每天,农夫John需要经过一些道路去检查牛棚N里面的牛.农场上有M(1<=M<=50,000)条双向泥土道路,编号为1..M.道路i连接牛棚P1_i和P2_i(1<=P1_i<=N;1<=P2_i<=N).John需要T_i(1<=T_i<=1,000, 查看详情
bzoj1579:[usaco2009feb]revampingtrails道路升级分层图+spfa
至死不用dijskstra系列2333，洛谷上T了一个点，开了O2才过基本想法是建立分层图，就是建k+1层原图，然后相邻两层之间把原图的边在上一层的起点与下一层的终点连起来，边权为0，表示免了这条边的边权，然后答案就是第0层的s... 查看详情
bzoj1579:[usaco2009feb]revampingtrails道路升级--分层图最短路
1579:[Usaco2009Feb]RevampingTrails道路升级TimeLimit: 10Sec MemoryLimit: 64MBDescription每天,农夫John需要经过一些道路去检查牛棚N里面的牛.农场上有M(1<=M<=50,000)条双向泥土道路,编号为1..M.道路i连接牛棚P1_i和P2_i(1<=P1_i 查看详情
bzoj1577:[usaco2009feb]庙会捷运fairshuttle
n<=20000个车站，车能同时载C<=100个人，求能满足K<=50000群人的多少个。每群人给起点终点和人数，一群人不一定要都满足。一开始想DP，想不出，很菜。贪心即可。如果有右端点相同的几群人，那肯定优先满足左端点大的；... 查看详情
bzoj3940[usaco2015feb]censoring*
bzoj3940[Usaco2015Feb]Censoring题意:有一个S串和一大堆T串，不断地在S串里找最早出现的T串，然后将其删除。S串≤100000，T串总长度≤100000。题解：对所有T串建AC自动机，然后同bzoj3942。注意，本题的AC自动机必须利用所有fail函数建成... 查看详情
bzoj3398/[usaco2009feb]bullcow牡牛和牝牛(代码片段)
Description 约翰要带N(1≤N≤100000)只牛去参加集会里的展示活动，这些牛可以是牡牛，也可以是牝牛．牛们要站成一排．但是牡牛是好斗的，为了避免牡牛闹出乱子，约翰决定任意两只牡牛之间至少要有K(O≤K<... 查看详情
bzoj3942[usaco2015feb]censoring*
bzoj3942[Usaco2015Feb]Censoring题意：有一个S串和一个T串，不断地在S串里匹配T串，然后将其删除。S串、T串长度≤1000000。题解：用1、2两个栈，每次将S串的当前字符压入1栈，当前匹配到T串的位置压入2栈，如果匹配出一个T串，则让1... 查看详情
贪心bzoj1577:[usaco2009feb]庙会捷运fairshuttle(代码片段)
一类经典的线段贪心Description公交车一共经过N（1<=N<=20000）个站点，从站点1一直驶到站点N。K（1<=K<=50000)群奶牛希望搭乘这辆公交车。第i群牛一共有Mi（1<=Mi<=N)只.他们希望从Si到Ei去。公交车只能座C（1<=C<=100）... 查看详情
bzoj3398[usaco2009feb]bullcow牡牛和牝牛：dp前缀和优化
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3398题意： 约翰要带N(1≤N≤100000)只牛去参加集会里的展示活动，这些牛可以是牡牛，也可以是牝牛。 牛们要站成一排。但是牡牛是好斗的，为了避免牡牛闹出乱子，约翰决... 查看详情
bzoj1577:[usaco2009feb]庙会捷运fairshuttle——小根堆+大根堆+贪心
Description公交车一共经过N（1<=N<=20000）个站点，从站点1一直驶到站点N。K（1<=K<=50000)群奶牛希望搭乘这辆公交车。第i群牛一共有Mi（1<=Mi<=N)只.他们希望从Si到Ei去。公交车只能座C（1<=C<=100）只奶牛。而且不走重... 查看详情