Posted on 2009-02-11 18:27
hello_world 阅读(1499)
评论(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)的,不过我暂时还没有想到!