51nod-1092 回文字符串

发表于 DP 分类,标签:
 回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。每个字符串都可以通过向中间添加一些字符,使之变为回文字符串。例如:abbc添加2个字符可以变为acbbca,也可以添加3个变为abbcbba。方案1只需要添加2个字符,是所有方案中添加字符数量最少的。Input输入一个字符串Str,Str的长度 <= 1000。Output输出最少添加多少个字符可以使之变为回文字串。Input示例abbcOutput示例2思路:将输入的字符串s1倒转后变成s2,然后求s1和s2的最长公共子序列的长度,然后将s1字符串的长度减去公共子序列的长度就是最后需要输出的答案。代码:#include<bits/stdc++.h>using namespace std;#define LL lo...

字符混编

发表于 DP 分类,标签:
 A、B和C。如果C包含且仅包含来自A和B的所有字符,而且在C中属于A的字符之间保持原来在A中的顺序,属于B的字符之间保持原来在B中的顺序,那么称C是A和B的混编。实现一个函数,判断C是否是A和B的混编。给定三个字符串A,B和C,及他们的长度。请返回一个bool值,代表C是否是A和B的混编。保证三个串的长度均小于等于100。测试样例:"ABC",3,"12C",3,"A12BCC",6返回:true代码:class Mixture {public:    bool chkMixture(string A, int n, string B, int m, string...

C(m,n)

发表于 DP 分类,标签:
 瞬间移动  Accepts:1018  Submissions:3620 TimeLimit:4000/2000MS(Java/Others)  MemoryLimit:65536/65536K(Java/Others)ProblemDescription有一个无限大的矩形,初始时你在左上角(即第一行第一列),每次你都可以选择一个右下方格子,并瞬移过去(如从下图中的红色格子能直接瞬移到蓝色格子),求到第nn行第mm列的格子有几种方案,答案对10000000071000000007取模。Input多组测试数据。两个整数n,m(2\leqn,m\leq100000)n,m(2≤n,m≤100000)Output一个整数表示答案SampleInput4 5SampleOutp...

钥匙计数之二

发表于 DP 分类,标签:
 钥匙计数之二时间限制(普通/Java):1000MS/10000MS     运行内存限制:65536KByte总提交:62      测试通过:38描述一把钥匙有N个槽,2<N<26槽深为1,2,3,4,5,6。每钥匙至少有3个不同的深度且相连的槽其深度之差不得为5。求这样的钥匙的总数。 输入输入数据由多行组成,每行包含一个整数n,表示该测试实例的锁匙有n个槽(1<n<=32)。输出对于每个测试实例,请输出满足要求的锁匙的总数,每个实例的输出占一行。样例输入 345 样例输出 1049045880 设lock[i]表示:有i个槽的钥匙的个数设one[i]表示:有i个槽且...

钥匙计数之一(详细过程)

发表于 DP 分类,标签:
 HDU1438 钥匙计数之一ProblemDescription一把锁匙有N个槽,槽深为1,2,3,4。每锁匙至少有3个不同的深度且至少有1对相连的槽其深度之差为3。求这样的锁匙的总数。 Input本题无输入 Output对N>=2且N<=31,输出满足要求的锁匙的总数。 SampleOutputN=2: 0N=3: 8N=4: 64N=5: 360..............N=31: ...分析a[i]表示长度为i的合法的钥匙总数。b[i]表示第i个槽为1或4时合法的长度为i的合法的钥匙总数。c[i]表示:不合法的长度为i-1的钥匙X+最后一个新槽1/4(1或者4的槽),能够构成合法的长度为i的钥匙时,不合法的长度...