题目链接：http://poj.org/problem?id=1088
DP初学者的好题，题意也简单，找2维数组，最长降序数列。
DP解题的经典问题，利用记忆搜索，也是我们平常的递归运算。
讲一下思路，递归4方向搜索，求最大的数，我利用的一个方向数组来完成四个方向的！
其中，两个问题拦住了我的AC，
第一个先开始，纯利用递归，导致重复计算量过大，TLE了，我们观察下其实每个点开始的最长降序数列的长度都是固定的，我们利用dp数组储存每个点的信息，可以避免重复计算，
第二个是，我在dfs函数中先开始，判断的条件是
1 | if(map[m][n]>0) |
1 | if(m>=1&&m;<=c&&n;>=1&&n;<=r) |
1 | /*************************************** |
题目链接：http://poj.org/problem?id=1080
不错的DP题，做了好多DP了，越做越觉得DP思路真的很开阔，以后还要加强，这题我参考的别人的解题报告，加以自己的想法。
解释下题意，两个字符串，通过增加空格来调整字符串，使得对应字符得到的数相加最大，比如题目中的
AGTGATG
-GTTA-G
第二列解释通过增加两个空格才和第一列对应的，一一对应关系参照
可得到最大的得分(-3)+5+5+(-2)+5+(-1) +5=14
我们可以看到，相同的字符是得分最大的，那么我们可以想到LCS问题，这题也算是LCS的一种变形。
解释下DP思路，dp[i][j]记录第一列i个字符和第2列j个字符开始的最大得分，这个得分也就是前面可能的三种情况的最大值！我们来举个例子：
比如i和j分别指字符G，C
那么有三种情况：
GXXX
CXXX
那么dp[i][j]=dp[i-1][j-1]+getmatch(str1[i-1],str2[j-1])
-GXX
CXXX
那么dp[i][j]=dp[i][j-1]+getmatch(str2[j-1],’-‘)
GXXX
-CXX
那么dp[i][j]=dp[i-1][j]+getmatch(str1[i-1],’-‘)
这样由dp[0][0]开始动态规划下去就是了，其中还要注意i，j分别等于0的情况，一面i-1，j-1不存在。
代码种getnum函数将字符转换数字getmatch将组合转换成得分
具体见代码：
1 | /*************************************** |
题目链接：http://poj.org/problem?id=2244
这个题简单约瑟夫问题，跟1012一个意思，不过比1012简单，方法一样，稍微调整一些细节就可以了。
题意是有n个城市，每隔m隔城市限电，1号第一个，问m为多少2号最后限电，我们可以这样看，就是n-1个城市从第一个开始数，保证第一个城市有电！
老样子利用公式：
1 | p[i]=(p[i-1]+m-1)%(n-i); |
代码如下：
1 | /*************************************** |
题目链接：http://poj.org/problem?id=2209
水题，就是求n个数的e次幂，如何加最大！必然是不加负数就是了！
代码如下：
1 | /*************************************** |
题目链接：http://poj.org/problem?id=1326
题意就是要求我们计算飞机的总费用，地名只是眼子，不用管，头等舱两倍于路程的价格，商务舱1.5倍于路程的价格，经济舱，若路程小于500按500算，1倍于路程的价格！0结束一次飞行，#结束程序！
简单模拟题，不过有一点，我觉得学会了一些东西，就是：
Hint
When calculate bonus ,be sure you rounded x.5 up to x+1
当我们用int()强制转换时电脑会默认去掉小数，如何利用电脑去4舍5入，也算是这个题的一个考点了，我们巧妙的加上0.5就可能让电脑将尾数在5后的数识别到下一个整数里。
详细可以参见代码：
1 | /*************************************** |
题目链接：http://poj.org/problem?id=1316
解释下题意，如果一个数可以写成另一个数及其个个位数的和，那么就不符合条件，比如39可以写成33+3+3那么不符合条件，要求输出所有符合条件的10000以内的数！
简单枚举，没什么算法，直接上代码：
1 | /*************************************** |
转眼又是一年的七夕了，说实话，相对于外国的情人节我还是比较喜欢七夕这个属于我们自己的节日，说来惭愧，没有佳人相伴，七夕也没什么特别的。
有时在忧郁大学要不要谈个朋友，也是通过一些方面知道一个朋友的女友陪他一起泡图书馆，想来那感觉应该不错，值得羡慕，不过谈个朋友又怕纠结，小K很优秀，我也很喜欢她但是还是没有一个好的结果，懒得伤害别的女孩了，想想，大学混混也就过了，让充实的生活满足自己的无聊也是可以的，说实话，不像以前，慢慢知道就业压力大的，虽然总跟爸妈说不用他们操心，但是自己还是有点小无奈的！
虽然下学期也快到了，计划也还行，但是我是个按计划来的人吗？显然不是，顺其自然吧，不然就不是我风格了！
不过我没有忘记老段对我说的，既然你不愿意复读，那么大学就好好搞吧，一样有番作为，他说担心我会为一些东西分心，我说不会的，他说，如果大学真的碰到一个不错的女孩不要错过，那时一辈子的后悔，我深刻记得这句话，并且牢记在心！
题目链接：http://poj.org/problem?id=1401
解释下题意，求n！后面有多少个0？比如10的阶乘是3628800那么就输出2！
有人说这个题是水题，其实只是题目简单，要在一个简单的题目里找到好的思路还是很有难度的！
分析下题目，有多少个0就是要求有多少含10的因式，也就是2*5的，但是其中含有的2绝对比5多，那么其实就是求，因式中有多少5
我现开始的思路就是将阶乘的每一个数都计算一次，每一个求因式5的数量，但是这样的方法在1000000000的数字下TLE了
贴下超时代码：
1 |
|
题目链接：http://poj.org/problem?id=1281
解释下题意，先输入最大的数，再输入最后查询移出数的个数，依次输入查询移出数的位置，后面就是循环的操作了；
我们以给出的例子来分析
Sample Input
5
2
1 3
a 2
a 3
r
a 4
p 2
r
a 5
r
e
最大值设为5，后面要查询两个数，分别是第1个和第3个，然后开始循环
a2a3—现在列表为2，3
r——p为1，删除最小的，现在列表为3，移出列表为2
a4—–现在列表为3，4，移出列表为2
p2—–p设为2
r——p为2，删除最大的，现在列表为3，移出列表为2，4
a5—–现在列表为3，5，移出列表为2，4
r——p为2，删除最大的，现在列表为3，移出列表为2，4，5
e——结束
然后输出第1个和第3个移出的，既2，5。
模拟题没什么好说的，他说什么你就干什么，利用数组inum记录查询的位置，inow记录现在数列里的数，idel记录删除的数，用inumx，inowx，idelx分别记录每个数组里的数的个数。话不多说看代码，很好理解。
代码如下：
::cpp
/***************************************
Problem: 1281 User: awq123
Memory: 700K Time: 0MS
Language: C++ Result: Accepted
***************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int cmp(int a,int b)
{
return a>b;
}
int main()
{
int inum[10000],inow[10000],idel[100000];
int imax,i,p,inumx,inowx,idelx;
char judge;
while(cin>>imax>>inumx)
{
p=1,inowx=0,idelx=0;
for(i=0;i<inumx;i++)
cin>>inum[i];
while(1)
{
cin>>judge;
if (judge=='e')
break;
else if (judge=='a')
{
cin>>inow[inowx];
inowx++;
}
else if (judge=='r')
{
if(p==1)
sort(inow,inow+inowx,cmp);
else if(p==2)
sort(inow,inow+inowx);
inowx--;
idel[idelx]=inow[inowx];
idelx++;
}
else if (judge=='p')
{
cin>>p;
}
}
for (i = 0; i < inumx; i++)
{
if(inum[i]>idelx)
cout<<-1<<endl;
else
cout<<idel[inum[i]-1]<<endl;
}
cout<<endl;
}
}
题目链接：http://poj.org/problem?id=1218
做了才知道为什么说这题式用来调节心情的，呵呵，话不多说，直接开方就是了。
不过第一次提交CE没办法，现在都用g++，还是有点区别的，c++里sqrt直接开int会编译错误，后来改成double，AC！
代码如下：
1 | /*************************************** |