usaco silver刷水~其实是回顾一下,补题解

【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】泥泞的路 贪心

按照左端点排序,尽量覆盖,贪心。

上一篇:应用.Net+Consul维护RabbitMq的高可用性


下一篇:javascript脚本化文档