【BZOJ】1601: [Usaco2008 Oct]灌水（kruskal）
http://www.lydsy.com/JudgeOnline/problem.php?id=1601很水的题，但是一开始我看成最短路了T_T果断错。我们想，要求连通，对，连通！连通的价值最小！当然是生成树！最小生成树！边的还好做，但是这题有点，怎么办呢？因为点在图中也起到连通作用，我们加个附加源...
POJ3621或洛谷2868 [USACO07DEC]观光奶牛Sightseeing Cows
一道\(0/1\)分数规划+负环POJ原题链接洛谷原题链接显然是\(0/1\)分数规划问题。二分答案，设二分值为\(mid\)。然后对二分进行判断，我们建立新图，没有点权，设当前有向边为\(z=(x,y)\)，\(time\)为原边权，\(fun\)为原点权，则将该边权换成\(mid\timesti...
[bzoj1692] [Usaco2007 Dec]队列变换 (hash||暴力)
本题同bzoj1640。。。双倍经验双倍幸福虽然数据范围n=3w然而O(n²)毫无压力==http://blog.csdn.net/xueyifan1993/article/details/7773750只要比较两个字符串的大小就行了==果断hash？具体一点的话就是从前往后和从后往前各hash一遍...
USACO Ski Course Design 暴力
从Min到Max范围内暴力一下即可。/*ID:wushuai2PROG:skidesignLANG:C++*///#pragmacomment(linker,"/STACK:16777216")//forc++Compiler#include<stdio.h>#include<io...
[BZOJ1597][Usaco2008 Mar]土地购买（斜率优化）
Description农夫John准备扩大他的农场,他正在考虑N(1<=N<=50,000)块长方形的土地.每块土地的长宽满足(1<=宽<=1,000,000;1<=长<=1,000,000).每块土地的价格是它的面积,但FJ可以同时购买多快土地.这些土地的价格是...
2018.09.10 bzoj1597: [Usaco2008 Mar]土地购买（斜率优化dp）
传送门终究还是通宵了啊。。。这是一道简单的斜率优化dp。先对所有土地排序，显然如果有严格小于的两块土地不用考虑小的一块。于是剩下的土地有一条边单增，另外一条单减。我们假设a[i]是单减的，b[i]是单增的。f[i]=min(f[j]+a[j+1]∗b[i])"role="presentation"s...
BZOJ1597: [Usaco2008 Mar]土地购买(dp 斜率优化)
题意题目链接Sol重新看了一遍斜率优化，感觉又有了一些新的认识。首先把土地按照\((w,h)\)排序，用单调栈处理出每个位置第向左第一个比他大的位置，显然这中间的元素是没用的设\(f[i]\)表示买了前\(i\)块土地的最小花费\(f[i]=min_{j=0}^{i-1}(f[j]+w[i]*h[j...
BZOJ 1626 [Usaco2007 Dec]Building Roads 修建道路：kruskal（最小生成树）
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1626题意：有n个农场，坐标为(x[i],y[i])。有m条原先就修好的路，连接农场(a[i],b[i])。现在要修一些路（首尾连接两个农场，长度为欧几里得距离），使得所有农场互相连通。问修路...
USACO Section 2.1 Healthy Holsteins
/*ID:lucien23PROG:holsteinLANG:C++*/#include<iostream>#include<fstream>#include<vector>usingnamespacestd;boolcompFun(intx,inty){intt...
洛谷P2687 [USACO4.3]逢低吸纳Buy Low, Buy Lower
P2687[USACO4.3]逢低吸纳BuyLow,BuyLower题目描述“逢低吸纳”是炒股的一条成功秘诀。如果你想成为一个成功的投资者，就要遵守这条秘诀:"逢低吸纳,越低越买"这句话的意思是：每次你购买股票时的股价一定要比你上次购买时的股价低.按照这个规则购买股票的次数越多越好，看看你最多能按这...
BZOJ1612: [Usaco2008 Jan]Cow Contest奶牛的比赛
1612:[Usaco2008Jan]CowContest奶牛的比赛TimeLimit: 5Sec MemoryLimit: 64MBSubmit: 645 Solved: 433[Submit][Status]DescriptionFJ的N(1<=N<=100)头奶牛们最近参加了场...
USACO 6.5 All Latin Squares
AllLatinSquaresAsquarearrangementofnumbers1234521453345124523153124isa5x5LatinSquarebecauseeachwholenumberfrom1to5appearsonceandonlyonceineachrowandco...
BZOJ_1626_[Usaco2007_Dec]_Building_Roads_修建道路_(Kruskal)
描述http://www.lydsy.com/JudgeOnline/problem.php?id=1626给出\(n\)个点的坐标,其中一些点已经连通,现在要把所有点连通,求修路的最小长度.分析已经连好一些边的最小生成树问题.这里顺带复习了一下Prim和Krusakal.Prim的证明:设当前已经...
BZOJ 1597: [Usaco2008 Mar]土地购买 [斜率优化DP]
1597:[Usaco2008Mar]土地购买TimeLimit: 10Sec MemoryLimit: 162MBSubmit: 4026 Solved: 1473[Submit][Status][Discuss]Description农夫John准备扩大他的农场,他正在考虑N(1<=N...
[BZOJ1609] [Usaco2008 Feb] Eating Together麻烦的聚餐 (dp)
Description为了避免餐厅过分拥挤，FJ要求奶牛们分3批就餐。每天晚饭前，奶牛们都会在餐厅前排队入内，按FJ的设想所有第3批就餐的奶牛排在队尾，队伍的前端由设定为第1批就餐的奶牛占据，中间的位置就归第2批就餐的奶牛了。由于奶牛们不理解FJ的安排，晚饭前的排队成了一个大麻烦。第i头奶牛有一张标...
USACO CHAPTER 1 1.1 Ride 水题
水题，主要是学习文件输入输出。/*ID:ijustwa1LANG:C++TASK:ride*/#include<cstdio>#include<cstring>usingnamespacestd;constintbase=;constintmod=;chars[];chart...
usaco /the first wave
bzoj1572:贪心。先按时间顺序排序，然后用优先队列，如果时间不矛盾直接插入，否则判断队列中w最小的元素是否替换掉。（没用llWA了一次#include<cstdio>#include<cstring>#include<iostream>#include<...
BZOJ 1668: [Usaco2006 Oct]Cow Pie Treasures 馅饼里的财富
Description最近，奶牛们热衷于把金币包在面粉里，然后把它们烤成馅饼。第i块馅饼中含有Ni(1<=Ni<=25)块金币，并且，这个数字被醒目地标记在馅饼表面。奶牛们把所有烤好的馅饼在草地上排成了一个R行(1<=R<=100)C列(1<=C<=100)的矩阵...
P2954([USACO09OPEN]移动牛棚Grazing2,dp)
题意概括有(n)个奶牛,(s)个牛棚,要求每个奶牛只能距离为(d)或(d1),(d=(n-1)/(s-1)),问奶牛的最小移动距离先把奶牛的位置排个序经过思考可以发现第一头奶牛在牛棚(1),第(n)头奶牛在牛棚(s),奶牛间的距离只能是(d)或(d1),且题目要求距离尽可能大那距离为(d)的数量和距...
洛谷 P2871 [USACO07DEC]手链Charm Bracelet 题解
题目传送门这道题明显就是个01背包。所以直接套模板就好啦。#include<bits/stdc++.h>#defineMAXN30000usingnamespacestd;intf[MAXN],w[MAXN],c[MAXN],n,v;intmain(){scanf("%d%d",&...