棒球投手 Pitcher Rotation
UVA1379定义：$Map[i][j]$为对战第$i$支队伍时，胜率排名第$j$位的棒球手的胜率$Schedule[i]$为第$i$天的对手$dp[i][a][b][c][d]$为考虑到前$i$天时，第$i$天派出胜率排名第$a$位，第$i-1$天派出第$b$位，第$i-2$天派出第$c$位，第$i-3$天派出第$d$位选手时的最大期望值。因为选手比赛后需要$Reset$至少4天，所以需要4天的派遣情况才能去重并使状态唯一。转移方程：
if(Schedule[i])\\dp[i][a][b][c][d] = max(dp[i][a][b][c][d], dp[i-1][b][c][d][e] + Map[Schedule[i]][a].Val)\\(1\leq a,b,c,d,e\leq 5)\\else\\dp[i][0][a][b][c] = max(dp[i-1][0][a][b][c], dp[i-1][a][b][c][d])\\(1\leq a,b,c,d\leq 5)如果第$i$天有比赛，则枚举第$i$个人应该派遣谁，并选取由最优的子状态转移过来。（因为选手休息4天又能 ...
照亮体育馆 Barisal Stadium
UVA10641题目为逆时针顺序编号，这里直接将数组开两倍来处理环。（然而不知为啥开到1000也能过）定义：$Corners[i]$为体育馆点的坐标。$Lights[i]$为灯的坐标及费用。$IsShineOn_{Cur}[i]$表示第$Cur$盏灯是否能照到$i$，用于计算范围。$Range_{Cur}$为第$Cur$盏灯的照射范围，从$Left$到$Right$，用于初始化$dp$$dp[Left][Right]$为从第$Left$盏灯照到第$Right$盏灯的最少花费。
初始化$\pmb{IsShineOn_{Cur}[i]}$：令$A、B$两点为体育馆的两点，$C$为体育馆的一盏灯，那么$C$要想照亮边$AB$，那么必须有$0^{\circ}< ∠BAC< 180^{\circ}$（手动转一转就知道了）因为有：
sin(∠BAC)=\vec{AB}×\vec{AC}$$并且当$sin\theta>0$时，$\theta\in(0^{\circ},180^{\circ})$。
因此只要叉乘大于0即可。注意是逆时针的顺序。
1234567891011121314//Cu ...
电子人的基因 Cyborg Genes
UVA10723有两个字符串$S_1,S_2$，求能包含他们的最短串。显然$S_1+S_2$可以包含$S_1$，又包含$S_2$，但是却不一定是最短的。为什么呢？因为$S_1,S_2$中有公共的子序列，这些子序列实际上最后只需要出现一次，而非两次。在$S_1+S_2$中就把这些公共的子串被计算了两次。比如样例中的ABAAXGF和AABXFGA，最长公共子序列为ABXG，而$S_1+S_2$为ABAAXGFAABXFGA，可以看到ABXG分别在$S_1,S_2$的部分中各出现了一次，而实际上我们只需要它出现一次即可。所以去掉一组ABXG得到AAFAABXFGA或ABAAXGFAFA都可以包含$S_1,S_2$，因此答案为$|S_1|+|S_2|-最长公共子序列长度$。因为得到的最短字符串为为$S_1+S_2-最长公共子序列$，而$S_1,S_2$是固定的，因此，解的数量为最长公共子序列的数量。定义：$dp1[i][j]$为考虑$S_1$前$i$个字符，$S_2$前$j$个字符的最长公共子序列长度，$dp2[i][j]$为最长公共子序列的数量。初始化：
dp1=0\\dp2[i][0]=d ...
禁止的回文子串 Dyslexic Gollum
UVA1633一个长的回文串都可以由短的回文串拓展而来，只要短的回文在左右两端增加相同的字符即可。因此，在考虑长度为$N$的01串时，只要在从长度为1向$N$拓展的过程中，保证后$K$个字符不是回文串即可。定义：$dp[i][j]$为考虑长度为i的串的后$K$个字符组成的子串为$j$时的合法字符串的数量。$IsPalindrome[i][j]$为长度为$i$的字符串$j$是否为回文串。由于$K\leq 10$，小于$int$的32为并且为01串，可以用一个$int$来保存字符串$j$，进行状态压缩。
求IsPalindrome初始化：
IsPalindrome[1][0]=dp[1][1]=true\\IsPalindrome[2][0]=dp[2][3]=true即0，1，00，11为回文串。转移方程：
IsPalindrome[i][j]=IsPalindrome[i-2][j去掉第一个字符和最后一个字符形成的子串]\\\&\&\\(j的第一个字符==j的最后一个字符)典型的中心拓展法，一个回文串如果左右各增加一个相同的字符，则形成的新字符串仍然是回文串。
求dp初始化：
dp[0 ...
算法杂题（思维、模拟）
题目链接@[toc]
A - やめて嘘はあなたらしくないよ
The $h$-index of an author is the largest $h$ where he has at least $h$ papers with citations not less than $h$. Bobo has published many papers. Given $a_0, a_1, a_2, \dots, a_{n}$ which means Bobo has published $a_i$ papers with citations exactly $i$, find the $h$-index of Bobo. Input The input consists of several test cases and is terminated by end-of-file.The first line of each test case contains an integer $n$.The second line contains $(n+1)$ integers $a_0, a_1, ...
软光栅算法和分型几何的实现
第一部分软光栅(1)绘制线段1 思路
如上图所示，当画一条线时，首先计算增量dx，dy。如果dy<dx，则x方向增长快，每次必加1，而y看判别式。
取dx所在线（x轴平行线）和画的线所成角的角平分线，若新的y落在该平分线上面，则y递增，否则y不变。而角平分线方程为：$dy=\frac{1}{2}dx$，即平分斜率。即$dy-\frac{1}{2}dx>0 \Longrightarrow 2dy-dx>0$时，y递增。此时下一个判别式的增量为$2(dy-dx)$。否则增量为$2dy$。
为了将直线扩展到所有斜率使用，实现使用了动态增量。
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960function drawLine(p1, p2){ var x1 = p1[0], y1 = p1[1]; var x2 = p2[0], y2 = p2[1]; /// 下方代码用以绘制线段 //由 ...
阿里巴巴 Alibaba
UVA1632这是一个区间动态规划定义：$dp[i][j][0]$为阿里巴巴收集完$i$到$j$的宝藏后位于$i$位置的最短耗时，$dp[i][j][1]$为阿里巴巴收集完$i$到$j$的宝藏后位于$j$位置的最短耗时。（在最短耗时情况下，阿里巴巴收集完某个区间的宝藏后只能位于区间的边缘，不可能在内部，因为在内部的话，必有重复经过的点，而在边缘，直接从一端到另一端即可）。初始化：
dp[i][i][0/1]=0即阿里巴巴在某地都可以瞬间收集宝藏。转移方程：12345678910111213141516171819dp[i][j][0] = min( //从i+1处向左走到i dp[i + 1][j][0] + Treasures[i + 1].Location - Treasures[i].Location, //从j处向左走到i dp[i + 1][j][1] + Treasures[j].Location - Treasures[i].Location ); //如果最短时间超时，则设为不可达 if (dp[i][j][0] >= Treasures[i].Limi ...
除法表达式
Time Limit(Common/Java):1000MS/10000MS Memory Limit:65536KByteTotal Submit: 279 Accepted: 68Description给出如下除法表达式E：X1/X2/X3/…./Xk其中Xi是正整数并且Xi<=2 000 000 000(1<=i<=k,k<=10 000)。除法表达式应当按照从左到右的顺序求结果，例如表达式1/2/1/2的值是1/4。现在让你可以在表达E中嵌入括号以改变计算顺序，例如表达式(1/2)/(1/2)的值是1。现在给你一个除法表达式E，要求告诉是否能够通过加括号（或者不加）得到表达式E’ ，E’的值为整数。 Input输入数据包括多组数据，每组数据占一行，给出的是题目描述的表达式E，E中不含空格。Output每个测试数据占一行如果能找到题目中描述的E’ 则输出”YES”（不含引号），否则输出”NO” (不含引号)。Sample Input 1/2/1/22/3 Sample Output YESNO SourceTOJUpload ...
