Best Reward Problem's Link:   http://acm.hdu.edu.cn/showproblem.php?pid=3613   Mean:  给你一个字符串，每个字符都有一个权值(可能为负)，你需要将这个字符串分成两个子串，使得这两个子串的价值之和最大。一个子串价值的计算方法：如果这个子串是回文串，那么价值就是这个子串所有字符权值之和；否则价值为0。

题目来源：HDU 3613 Best Reward 题意：每个字母对应一个权值 将给你的字符串分成两部分 如果一部分是回文 这部分的值就是每个字母的权值之和 求一种分法使得2部分的和最大 思路：考虑扩展KMP 输出a串 得到a的反串b 求出f[0]和f[1] 和 extend[0]和extend[1] 正反求2次 枚举位置i 分成2部分0到i-1 和i到n-1 因为分成的2部分必须组成原字符

#include<iostream>#include<cstdio>#include<cstring>#include<map>using namespace std;int N,T,S,E,num;map<int,int> mp;struct Matrix{int ma[210][210];void clear(){memset(ma,0x3f,sizeof(ma)); //初始化一定要

Cow Relays Time Limit: 1000MS Memory Limit: 65536KTotal Submissions: 5611 Accepted: 2209 Description For their physical fitness program, N (2 ≤ N ≤ 1,000,000) cows have decided to run

题意：有n个星球，其中有些星球上有多个工作，有些星球上有些资源（但是一个星球上的资源只能提供给一个工厂），知道在一些星球边建立边的代价，问使得得到资源的工厂的数目最多的多少，在些前提下代价最小是多少。 还是斯坦纳树，不懂看：http://endlesscount.blog.163.com/blog/static/821197872012525113427573/ #include <iost

POJ 3613 Cow Relays POJ 3613 Cow Relays 真心想吐槽一下，这个不能用 11 11 11 真的挺难受的。 首先看去像一个板子题，之后发现如果直接对于每个点建图的话时间是过不了的。 之后发现边的数量其实不是很多，一条边最多只有两个不同的点，所以实际上有用的点数是 2 m + 2 2m + 2 2m+2 个。我们对于这个直接进行矩阵快速幂

本题的大意就是问从S 到 T 经过边得个数恰为k的最短路是多少。 参考国家队集训论文 08年的  矩阵乘法在信息学中的应用 01邻接矩阵A的K次方C=A^K,C[i][j]表示i点到j点正好经过K条边的路径数  对应于这道题,对邻接图进行K次floyd之后,C[i][j]就是点i到j正好经过K条边的最短路 但是K次floyd难免复杂度太高了。 所以可以使用快速幂的方法，二分的往上求