posts - 11, comments - 2, trackbacks - 0, articles - 0

 

题目分类
 Bridge  过桥问题
 Saskatchewan  离散化(geometry)
 Jolly Jumpers  水题
 Tug of War  DP
Interpreter 模拟

bridge:
http://www.cnblogs.com/drizzlecrj/archive/2007/11/24/931011.html

这篇文章有讲解还有配套的题目,我不罗嗦了



Saskatchewan:
我是枚举每列, 然后计算这一列的面积,再加起来就可以了
一列中,先删去不在当前范围内的边,再把剩下的边排序,然后从低到高成对的考虑即可
还有能不用 stl 的就尽量不用,很慢
其实只要想到离散化就很简单了~~


Tug of War:
 这个题目貌似有很多解法,我是这样做的:
dp[k][i][j]代表前k个人分成两边,其中一边有i个人重量为j的状态是否可以达到!
那么dp[k][i][j]=true if and only if dp[k-1][i-1][j-H[k]]=true;其中0<=k<=100;0<=i<=50;0<=j<=450*100;在题目给3s的情况下还是可以接受的!第一维只是方便理解,实现同样可以不管第一维!只要逆推就好了!
当处理完上面以后,假设n个人的总重量是s,最后只要从dp[n][n/2][0~s]中找到最接近s/2的那个状态就好了~



Interpreter:
典型的模拟题目,只要理解了题目意思照着写就可以了~
这里推荐一个类似的题但是难度可能要大一些:
http://202.120.80.191/problem.php?problemid=1840

 

题目分类
 Freckles  图论,最小生成树
   
  Primary Arithmetic  简单题
 Demerit Points 模拟
Edit Step Ladders DP加二分

Demerit Points:
直接按照题目模拟就好了,只是有点繁琐而已!

Edit Step Ladders:
跟LIS的动态规划一样,dp[i]表示到前前i个单词最长的,那么dp[i]=max(dp[j])+1;(0<=j<i,且word[j]可以由规则变成word[i]);转移的时候我们可以让word[i]通过规则生成单词,看该单词是否在前面出现过!注意我们没必要生成所有的单词,因为有序,我们只需要生成比word[i]小的单词!查单词的时候可以二分查找!
后面讨论说可以nlog(n)的,不过我暂时还没有想到!


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理