流浪的枫之羽

题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=1159题目意思是：告诉你一个字符串，要求插入最少一个字符才能成为回文串！我现在的理解是用字符串与它的逆序求LCS，然后长度减去最大的LCS就是所求的！当然内存要用滚动数组保存！这个是我猜出来的，并没有经过严格的证明，不过在IOI2000的解题报告里已经证明了，有兴趣的可以去看看！链接：http://www.jjstudent.cn/oi/ShowArticle.asp?ArticleID=22首先介绍一下什么是滚动数组：滚动数组实际是一种节省空间的办法，时间上没啥优势，多用于DP中，举个例子吧： 一个DP，平常如果需要1000×1000的空间，其实根...

题目是LCS的问题，求最长公共子串！其实以前就AC过的题目，不过以前对于DP不是很熟悉，最近突然又萌发做题的念头，所以顺带着把它又AC了一遍！不过这确实是一道经典且简单动态规划 方法很简单，利用一个二维数组就能搞定！状态方程是f[j]=f[i-1][j-1]+1(s1==s2[j]) f[j]==max(f[i-1][j],f[j-1])(s1!=s2[j])题目链接：http://acm.zju.edu.cn/show_problem.php?pid=1733#include#include#includechar s1[1000],s2[1000];int f[1000][1000];int mmax(int a,int b){if(a>b) return a;else return b;}int main(){int i,j;int len1,len...

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1846题目描述:各位勇敢者要玩的第一个游戏是什么呢？很简单，它是这样定义的：1、   本游戏是一个二人游戏;2、   有一堆石子一共有n个；3、   两人轮流进行;4、   每走一步可以取走1…m个石子；5、   最先取光石子的一方为胜；这是一种最简单的取石子的游戏，通过推小范围数据就能把结果给推出来，不信你可以试试。以下是代码：#includeint main(){ int cas; int m,n; scanf(“%d”,&cas); while(cas–) { scanf(&#...

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1524游戏描述是你在一个有向图上有N棋子，你能将棋子进行移动，到棋子都移动到出度为0的顶点时就不能再移动，此时不能再移动的player就算输.这道题是最典型的有向图游戏的博弈，方法其实在ACM中的博弈游戏综述(2)中已经进行了介绍，做DFS深搜，把所有节点的SG值都算出来，然后对每个棋子的SG值进行异或运算，得出不等0就是WIN，0和的局面就是LOSE.下面是这道题目的算法代码#include#includeusing namespace std;//博弈加上深搜索int SG[1000],n;vectorarc[1000];void GetSgDfs(int i){bool Judg...

      上一期的文章里我们仔细研究了Nim游戏，并且了解了找出必胜策略的方法。但如果把Nim的规则略加改变，你还能很快找出必胜策略吗？比如说：有n堆石子，每次可以从第1堆石子里取1颗、2颗或3颗，可以从第2堆石子里取奇数颗，可以从第3堆及以后石子里取任意颗……这时看上去问题复杂了很多，但相信你如果掌握了本节的内容，类似的千变万化的问题都是不成问题的。现在我们来研究一个看上去似乎更为一般的游戏：给定一个有向无环图和一个起始顶点上的一枚棋子，两名选手交替的将这枚棋子沿有向边进行移动，无法移动者判负。事实上，这个游...