ACM

题目链接 题意：给出一个字符串，问所有不同的字串的个数。 思路：直接求比较困难。我们考虑，假如组成字符串的所有字符都不相同，那么就没有相同的字串，假设字符串的长度为n，那么长度为1的子串有n个，为2的有n-1个。。。为n的有1个，一共就是n*(n+1)/2个。。但是实际上会有重复的。。。

poj3261 题意：给一个字符串，要求找出至少出现k次的最长重复子串…

poj 1743 题意：n个数字（1..88）表示的音符，问最长的连续两段长度至少为5的变化相同的音符段的长度。。。

ural1517 题意：给出两个字符串，求最长的公共字串（要求出具体的字符串是什么）

poj2774 题意：给出两个字符串，问最长的公共连续字串。 思路：后缀数组模板题。

hdu1280 题意：给出n(3000)个数，两两求和，输出最大的m(5000)个和。

原文链接：链接 讲了后缀数组的概念，然后从最暴力的O(nnlogn )的复杂度(O(n)用来比较字符串，O(nlogn)是排序的复杂度)逐步优化，依据各个串之间的关系，大概讲了倍增算法，以及给出了一篇The Skew Algorithm 的论文。

1874: [BeiJing2009 WinterCamp]取石子游戏 # Time Limit: 5 Sec Memory Limit: 162 MB Submit: 726 Solved: 296 [Submit][Status][Discuss]

cf429 b 题目链接 题意： n*m个格子，每个格子有一个人value a[i][j]>0，连个人，一个从左上角到右下角，每次只能向下或者向右移动，一个从左下到右上，每次只能向上或者向右移动，现在要求两个人恰好相遇一次，相遇点的a不算数，问在满足这样的条件下使得两个人的a最大。。。（很坑的一点是。。这里相遇并不考虑时间。。就是说，不在同一时间都到达过某一格子，也认为相遇。所以我认为，题目含义更准确的说法是，路径只有一个交点）

hdu 2050题目链接 题意：n条折线。。最多能把平面分成几部分。。 思路：联想到m条直线，最多能把平面分成m*(m+1)/2+1部分。。

hdu 2049 题目链接 题意：n个妹子和n个汉子对应。。然后让每个汉子取选一个妹子，不能重复，问恰好有m个汉子选错妹子的可能的方案数。

。。。重新编译一次就可以了。。。orz

hdu2048 题目链接 题意:n个人不放回的从一个有n个每个人对应id的卡片的盒子取一张卡片，取的正好和自己的对应就算中奖。求所有人都没有中奖的概率。

hdu 2047 题目链接 题意：一个由’E’ ‘O’ ‘F’ 组成的长度为n的字符串。‘O’不能相邻。。问方案数。。

hdu2045 题目链接 题意： 一串 方格，每个格子可以涂三种颜色，要求相邻的格子颜色不能相同，首尾格子也不能相同。

hdu2018题目链接 题意:第1年有1头奶牛，每年生一头奶牛，新生的奶牛从生下来的第四年（包括生下来那年）也开始每年一头奶牛。 问第n年有多少头奶牛。 思路：最容易想到的。。递推一下。。。dp[i] = dp[i-1] + dp[i-3] (注意初始化不是一个dp[1]=1,而是dp[1..4]=1..4)

hdu2084题目链接 题意：dp入门题。。。数字三角形。。 思路： 昨天看mit公开课。。。讲到dp的精髓是sub-problem+ reuse…

hdu 4283题目链接 题意：有N个人按顺序排成一排上台表演，每个都有一个num[]值，若在他是第k个上场的人，则会有num[]*(k-1)的unhappiness。台下有一个黑屋（stack），对每一个人，可以选择让他先进屋子或者直接上台。现在让你找到一个最优方案使得所有人的unhappiness之和最小。

poj 3661题目链接 题意：锻炼，一共n分钟，每分钟可以选择跑步或者休息，第i分钟跑步可以跑d[i]米，并增加一点疲劳度，如果选择休息，那么每分钟减少1点疲劳值。一旦开始休息，必须休息到疲劳值为0才能再次开始跑步。疲劳值不能超过m.第n分钟的时候疲劳值必须为0，否则之后会感觉身体被掏空。问n分钟最远多多远。

poj 1651题目链接 题意：n个数，删掉a[i]的得分是a[i]*a[i-1]*a[i+1]，两个端点的不允许删。问删完n-2个数得到的最小分数是多少。