【BZOJ1606】【Usaco2008 Dec】Hay For Sale
裸01背包
for(int i=;i<=n;i++)
for(int j=m;j>=a[i];j--)
f[j]=max(f[j],f[j-a[i]]+a[i]);
【BZOJ1607】【Usaco2008 Dec】轻拍牛头
暴力
【BZOJ1609】【Usaco2008 Feb】麻烦的聚餐
要求最长上升子序列或最长下降子序列的长度。
最基础的有dp算法
for(int i=;i<=n;i++)
for(int j=;j<=;j++){
for(int k=;k<=j;k++)f[i][j]=min(f[i-][k],f[i][j]);
if(a[i]!=j)f[i][j]++;
}
还有比较优的算法，nlogn求解最长上升子序列
这里的lower_bound找第一个大于x的数
bool cmp1(int a,int b){return a<=b;}
for(int i=;i<=n;i++) {
int k=lower_bound(g+,g++n,a[i],cmp1)-g;
g[k]=a[i];
ans=max(ans,k);
}
【BZOJ1613】【USACO2007 Jan】贝茜的晨练计划 DP
For(int i=;i<=n;i++){
Dp[i][]=dp[i-][];
For(int j=;j<=m;j++){
Dp[i][]=max(dp[i][],dp[i-j][j]);
Dp[i][j]=max(dp[i][j],dp[i-][j-]+a[i]);
}
}
【BZOJ1622】【USACO2008 Open】名字的力量 暴力
N*M在字符串中找另一个字符串不需要连续
【BZOJ1623】【USACO2008 Open】奶牛飞车 贪心
因为速度要减去d(常数）*在前面的车数量，所以按速度从小到大，小的在前
【BZOJ1628】【USACO2007 Demo】City Skyline 堆
维护一个单调递增的栈，判断栈顶元素是否与a[i]相同
Ans=n;
For(int i=;i<=n;i++){
if(q[top]>a[i]&&top>）top--;
if(q[top]!=a[i])q[++top]=a[i];
else ans--;
}
【BZOJ1633】【USACO2007 Feb】牛的词典 DP
Dp[i]表示I后最少要删的字母个数，dp[i]=min(dp[i+1]+1,f[i+len[j]+t]+t);
T为I后要删除t个字母才能找到s[j]
f[i]=f[i+]+;
for(int j=;j<=n;++j){
int now=,t=;
for(int k=i;k<m;++k) {
if(words[j][now]==s[k]) ++now;
else ++t;
if(now==words[j].length())break;
}
if(now==words[j].length()) f[i]=min(f[i],f[i+t+now]+t);
}
【BZOJ1634】【USACO2007 Jan】护花 贪心
对于每头牛来说都有自己ti*di代价
对于相邻两头牛，差异在于2*ta*db和2*tb*da，故写出比较函数，排序即可。
【BZOJ1635】【USACO2007 Jan】最高的牛
利用前缀和的思想，对于x,y,sum[x+1]++;sum[y]--;
求前缀和，用最高的height减去。
【BZOJ1636】【USACO2007 Jan】Balanced Lineup
ST表
【BZOJ1637】【USACO2007 Mar】Balanced Lineup sort一下乱搞搞
对于0种族 -1，对于1种族+1，求前缀和，对于每一种前缀和标记最早出现的位置
1~n循环一下，取最大值。
【BZOJ1638】【USACO2007 Mar】奶牛交通 DAG上DP
正向dp到一个点的路径条数，反向dp一遍，对于每条边经过次数即前端点*后端点，取max
【BZOJ1639】【USACO2007 Mar】月度开支
二分贪心
【BZOJ1640】【USACO2007 Nov】队列变换 贪心
如果前后相等就继续比较较内的字符
【BZOJ1641】【USACO2007 Nov】奶牛跨栏 用类似Prim的方法预处理即可
Floyd
for(int k=;k<=n;k++)
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
f[i][j]=min(f[i][j],max(f[i][k],f[k][j]));
【BZOJ1642】【USACO2007 Nov】挤奶时间 DP
读入后，按照左端点排序,右端点直接加上等待时间。
F[I]表示第I个任务及以前的最大产奶量
f[i]=max(f[1]…f[i-1])+v[i]; (r[j]<=l[i])
【BZOJ1646】【USACO2007 Open】抓住那头牛 BFS
可以向前走，向后走，*2.
【BZOJ1648】【USACO2006 Dec】奶牛野餐
暴力DFS
【BZOJ1649】【USACO2006 Dec】Cow Roller Coaster DP
按照左端点排序，左端点相同排右端点
F[i][j]表示到I长度，成本为j
F[i][j]=max(f[i][j],f[a[i].l][j-a[i].c]+a[i[.f
【BZOJ1650】【USACO2006 Dec】跳石子
二分贪心
【BZOJ1651】【USACO2006 Feb】专用牛棚 堆贪心
a[l]+1,a[r+1]-1,求前缀和，取最大值
【BZOJ1688】【USACO2005 Open】疾病管理 状压DP
不知道为什么暴力时间复杂度不对，但就是过了
不过顺便学习了bitset(测试后发现时间上并没有比bool快多少(可能因为数据水
zyf-zyf:但是好写呀！
#include<bitset>
bitset<NUM> b;
bitset<NUM> b(int/string);
b.reset();清0
b.set();赋1
b.set/reset(pos);
b.count();1的个数
b.flip(pos/ /);取反
正解状态压缩dp~额，其实时间复杂度基本一样
用二进制表示每一头牛的得病情况
f[j|a[i]]=max(f[j|a[i]],f[j]+1)
【BZOJ1689】【USACO2005
Open】泥泞的路 贪心
按照左端点排序，尽量覆盖，贪心。