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