7 ascii991

尚未进行身份认证

暂无相关简介

等级
TA的排名 3w+

poj 2938 Economic Phone Calls

此题的核心就是选择,按时间顺序进行选择的话,可以发现每次选择只和当前选择的集合中时间最晚的电话有关。所以可以dp。令f[i][j]为处理了前i个电话,当前选择的电话中最晚的电话为j时,选择的最少电话数。对于i而言,如果选择i,则有f[i][i]=min{f[i-1][j]},其中1同时,如果i是今年的电话,则除了上面的转移,还有f[i][i]=min(f[i][i],f[i-1][

2012-08-18 16:25:22

poj 2817 wordstack

数据规模很小,不免让人想到搜索。但10!=3628800还是不够优秀。考虑到每次选择只与前一次选择有关,且N注意理解题意,允许两个单词中位置相同的字母不同,只是要求位置相同的字母相同的数目最大即可。可以在dp前做一些预处理。【代码】#include#include#include#include#includeusingnamespacestd;

2012-08-18 16:12:22

双调TSP问题总结---poj 2677和usaco5.4 canada tour

双调TSP指的就是从最左边的城市出发,从左往右遍历一些城市,到达最右端,再从最右端从右往左返回出发城市,然后最优化某些东西。poj2677就是要遍历所有的城市,最小化行走的距离(欧几里德距离)usacocanadatour就是每个城市最多遍历一次(出发点两次),最大化遍历的城市数量。【解答】显然从左往右,从右往左都是一样的,都可以变成从左往右。我们称前者为上行路线,后者为

2012-08-16 15:24:06

poj 2486 apple tree

显然是一道树上的分配问题。自然而然想到树上的背包。但要注意,这道题有两种情况。1、往下遍历,并最后返回根节点。2、往下遍历,并停留在某处结束,不返回根节点。令第一种为f[x],第二种为g[x]。求g[x]时,要枚举究竟是哪个儿子是往下遍历,最后停留在某处结束,不返回根节点的。所以复杂度为O(N*N*K*K)【教训】在叶子这里的边缘状态设置:f[x][0]=f[x

2012-08-14 14:22:12

POJ 2057 The lost house

这道题求的是期望。首先,一看到期望,就会想到可以将问题分成若干个子问题,再分开算期望,所以这道题可以使用动态规划。注意到每个叶子有房子的概率是均等的。所以答案就是遍历每个叶子最少的步数/叶子的总数。所以问题划归为求遍历所有叶子的最少步数。我们令fail[x]为以x为根的子树找不到房子的最少步数。su[x]为以x为根的子树中找到房子最少步数。le[x]为以x为根的子树中叶子的

2012-08-14 14:04:51

poj 1925 spiderman

首先,这道题有两种做法。第一种是先枚举位置,再枚举楼进行dp。第二种是先枚举楼,再枚举位置。然而蜘蛛侠的行进路线有对称性的。相当于将一号楼沿着某一座楼对称过来,就像镜子一样。根据对称性,蜘蛛侠在放出绳子时的高度永远是h[1]。因此,第二种方法中枚举位置时,可以根据蜘蛛侠所在的高度和楼的高度两个条件,缩小第二层枚举的范围。因此,第二中方法更加优秀。【代码】#include#inc

2012-08-14 13:38:22

APIO2007 数据备份 贪心+堆实现

【算法分析】n,k都有10^5,所以考虑贪心算法最基本的贪心就是任意一对数必须是相邻的,这是显然的。考虑到一重要结论:假设现在有三条相邻的线段a1,a2,a3;a1>a2,a3>a2,如果a2小于等于最优解集中的最大元素,并且最优解集中不存在a2,则必同时存在a1,a3。证明:如果最优解中只有a1或只有a3,那我可以把它换成a2,这组解仍然满足要求,但总距离更小。如

2012-08-04 13:59:13

poj 1038 状态压缩dp 四进制压缩

黑书上的牛逼题状态压缩,每个格子有0,1,2三种状态。0表示这个格子为空,1表示这个格子到下一行为空。2表示这个格子到下下一行为空。如果以(x,y)这个格子为左上角放2*3的矩形,则(x,y)=(x,y+1)=(x+1,y)=(x+1,y+1)=(x+2,y)=(x+2,y+1)=2。如果以(x,y)这个格子为左上角放3*2的矩形,则(x,y)=(x,y+1)=(x,y+2)=(x+1

2012-08-02 17:07:13

并查集练习---poj 2912

集合的合并与维护和食物链那道题一样。不过多了个裁判。注意到N如果有矛盾,则这个人不是裁判。唯一有点难度的是输出第几行判断出的裁判。原先以为是最后出现裁判的那一行。后来发现应当时枚举其他人时候首次出现矛盾的最大值。(仔细想想)这样这道题就解决了。【代码】#include#include#include#include#includeusing

2012-07-28 14:37:09

并查集练习---poj 1417 并查集+DP

这到题倒是和teamthemup有些类似。很容易得到:回答yes,则x和y是相同集合的,反之,则是不同集合的。首先用friend-enemy并查集,注意:不要将朋友和敌人分开维护,这样容易出错。得到了若干集合,每个集合有两个数,a和b。现在要求n个集合中各挑出一个数(a或者b),使得他们之和等于p1(说真话的人数)。而这个用dp可以很好的解决,用f[i][j]表示

2012-07-28 14:28:57

并查集练习---poj 1984

usaco的月赛题。记录两个点之间x方向和y方向的相对距离,用并查集维护。若与poj1182食物链进行比较,便会发现路径压缩部分,集合合并部分的相似点。所以并查集不难,是有一定套路可循的。大家一定要好好总结。【代码】#include#include#include#include#includeusingnamespacestd;consti

2012-07-28 14:20:21

并查集练习---poj 1182 食物链

经典的并查集题目。主要是节点之间的关系的维护。首先看路径压缩部分:intfind(intx){if(fa[x]==x)returnx;intt=fa[x];fa[x]=find(fa[x]);r[x]=(r[x]+r[t])%3;returnfa[x];}这里要注意保存原来的父节点。再看如何合并:fx=find

2012-07-28 14:15:52

线段树典型例题--poj2777

这到题我认为网上有些人的算法是不对的。voidsolve(intl,intr,introot)//询问{if(tree[root].col>=0)//如果父节点有单一的颜色,就直接更新,不需要找到子节点更新{flag[tree[root].col]=1;//统计哪些颜色出现过return;}if(t

2012-07-23 17:37:27

线段树典型例题--poj3667 hotel

题目很像内存分配。线段树维护这样几个量:col:节点的颜色(0--没有覆盖,1--全覆盖,-1--有多种颜色)dl:从左边开始的最长连续段dr:从右边开始的最长连续段dm:节点中的最长连续段dp:节点中最长连续段的开始位置具体见代码:#include#include#include#include#includeusingnamespaces

2012-07-23 17:22:37

线段树典型例题--poj3277

将x轴上的点离散化。y轴建立线段树。使用延迟标记。注意:延迟标记不是单纯覆盖,而是需要比较的。pp[i]为标记则应当是pp[i*2]=max(pp[i*2],pp[i]);pp[i*2+1]=max(pp[i*2+1],pp[i]);而不是pp[i*2]=pp[i*2+1]=pp[i];【代码】#include#include#include#incl

2012-07-23 17:16:35

线段树典型例题--poj2828

逆序处理。注意到如果逆序插入,则每次插入的位置都是第x个空位。所以可以用线段树来寻找第x个合法位置【代码】#include#include#include#include#includeusingnamespacestd;constintN=200005;intsum[N*3],pos[N],val[N],p[N];intn;void

2012-07-23 17:11:57

线段树典型例题--poj2528

此题的关键在于离散化。对于线段(a,b),要将a-1,a,b三个量都考虑进去。否则我们看这样一个例子:311013610答案是3如果不考虑a-1,则答案会变成2。【代码】#include#include#include#include#includeusingnamespacestd;constintN=1000

2012-07-23 17:09:06

线段树典型例题--poj2482

【题意】Assumetheskyisaflatplane.Allthestarslieonitwithalocation(x,y).foreachstar,thereisagraderangingfrom1to100,representingitsbrightness,where100isthebrightestand

2012-07-23 17:04:10

poj 贪心小结(一)

本次贪心题的练习题有:2325,3258,3122,2393,1065,1323,1328,17001700:经典的过河问题。两种贪心策略,一种是最快的+最慢的,最快的回来,再最快的+次慢的,最快的回来,第二种是最快的+次快的,次快的回来,再最慢+次慢过河,在最快的回来。两中策略的结果都是最慢的和次慢的过了河。然后就可以dp,注意n=1,2,3特判。2325:贪心+高精度3258:二分

2012-07-14 10:30:42

ural 1165 subnumber ------猥琐的超级大繁题

1165.SubnumberTimeLimit:1.0secondMemoryLimit:16MBGeorgelikesarithmeticsverymuch.Especiallyhelikestheintegersseries.Hismostfavouritethingistheinfinitesequenceofdigi

2012-07-11 14:50:52

查看更多

勋章 我的勋章
    暂无奖章