好的网站 具备,有源码手机怎么搭建网站,lamp 安装wordpress,做网站开发的营业执照顾名又思义#xff0c;是在字符串上进行的DP操作。因为字符串本身可以看作是一个序列#xff0c;所以有些时候字符串DP可以用区间DP来解决。P2246 SAC#1 - Hello World(升级版)题目描述在讲义的某一面#xff0c;他看见了一篇文章。这篇文章由英文字母(大小写均有)、数字、和…顾名又思义是在字符串上进行的DP操作。因为字符串本身可以看作是一个序列所以有些时候字符串DP可以用区间DP来解决。P2246 SAC#1 - Hello World(升级版)题目描述在讲义的某一面他看见了一篇文章。这篇文章由英文字母(大小写均有)、数字、和空白字符(制表/空格/回车)构成。pipapi想起了他最近刚刚学会写的Hello World程序。他非常好奇这篇文章中“HelloWorld”作为子序列到底出现过多少次呢由于papapi是个智障大小写对于他而言毫无区别因此“hEllOWorLD”这样的子序列也是可以接受的。O和W之间的空格是也是可以少的也就是说“HelloWorld”是可以的。根据标程的意思就是没有空格不用考虑空格的情况。两个子序列相同当且仅当它们每一个字符所在的位置都相同。由于答案可能很大请输出结果对1000000007(10^97)的余数。输入输出格式输入格式输入包含若干行。这些行的内容共同构成一篇文章。文章以EOF(文件结尾)结束。输出格式输出仅包含一个整数表示这篇文章中“Hello World”出现的次数。 d输入输出样例输入样例#1HhEeLlLlOoWwOoRrLlDd输出样例#11536输入样例#2Gou Li Guo Jia Sheng Si YiQi Yin Huo Fu Bi Qu ZhiRiver can feed peopleAlso can race boatsHall Ellen Ok Words locked输出样例#2273说明记n为输入的文章的长度(字符数)。对于20%的数据n 20。对于50%的数据n 500。对于所有的数据15 n 500000。入门题。设\(dp[i][j]\)表示文本串前i个字符匹配helloworld模板的前j个字符的匹配数。显然当\(a[i]b[j]\)时有\(dp[i][j]dp[i-1][j-1] dp[i-1][j]\),其他情况\(dp[i][j]dp[i-1][j]\)。前面一维直接滚动优化掉。#include #include #include #include #include using namespace std;typedef long long LL;const int MOD 1e9 7;char ch1[233] #helloworld;char ch2[233] #HELLOWORLD;int f[233];int main() {char x; f[0] 1;while ((x getchar())!EOF)for (int i 10; i 1; -- i)if (x ch1[i] || x ch2[i])f[i] (f[i-1] f[i]) % MOD;cout f[10] endl;return 0;}P2890 [USACO07OPEN]便宜的回文Cheapest Palindrome题目描述Keeping track of all the cows can be a tricky task so Farmer John has installed a system to automate it. He has installed on each cow an electronic ID tag that the system will read as the cows pass by a scanner. Each ID tags contents are currently a single string with length M (1 ≤ M ≤ 2,000) characters drawn from an alphabet of N (1 ≤ N ≤ 26) different symbols (namely, the lower-case roman alphabet).Cows, being the mischievous creatures they are, sometimes try to spoof the system by walking backwards. While a cow whose ID is abcba would read the same no matter which direction the she walks, a cow with the ID abcb can potentially register as two different IDs (abcb and bcba).FJ would like to change the cowss ID tags so they read the same no matter which direction the cow walks by. For example, abcb can be changed by adding a at the end to form abcba so that the ID is palindromic (reads the same forwards and backwards). Some other ways to change the ID to be palindromic are include adding the three letters bcb to the begining to yield the ID bcbabcb or removing the letter a to yield the ID bcb. One can add or remove characters at any location in the string yielding a string longer or shorter than the original string.Unfortunately as the ID tags are electronic, each character insertion or deletion has a cost (0 ≤ cost ≤ 10,000) which varies depending on exactly which character value to be added or deleted. Given the content of a cows ID tag and the cost of inserting or deleting each of the alphabets characters, find the minimum cost to change the ID tag so it satisfies FJs requirements. An empty ID tag is considered to satisfy the requirements of reading the same forward and backward. Only letters with associated costs can be added to a string.字串S长M由N个小写字母构成。欲通过增删字母将其变为回文串增删特定字母花费不同求最小花费。输入输出格式输入格式Line 1: Two space-separated integers: N and MLine 2: This line contains exactly M characters which constitute the initial ID stringLines 3..N2: Each line contains three space-separated entities: a character of the input alphabet and two integers which are respectively the cost of adding and deleting that character.输出格式Line 1: A single line with a single integer that is the minimum cost to change the given name tag.输入输出样例输入样例#13 4abcba 1000 1100b 350 700c 200 800输出样例#1900说明If we insert an a on the end to get abcba, the cost would be 1000. If we delete the a on the beginning to get bcb, the cost would be 1100. If we insert bcb at the begining of the string, the cost would be 350 200 350 900, which is the minimum.比较经典的字符串DP了。设\(dp[i][j]\)表示区间[i,j]变成回文串的最小花费需要用到区间DP的思想。考虑如何用一个小区间更新一个大区间。如果大区间是\(dp[i][j]\)若s[i]s[j]那么\(dp[i][j]dp[i1][j-1]\)即当前大区间可以由去掉其两端的小区间更新而来而不用花费。不等的时候\(dp[i][j]min(dp[i1][j]min(add[s[i]],del[s[i]]),dp[i][j-1]min(add[s[j],del[s[j]]])\)#include#includeusing namespace std;const int M 2005, N 256;int n, m;char c, s[M];int del[N], add[N], f[M][M];int main() {scanf(%d%d%s, n, m, (s1));for (int i 1; i n; i) {cin c;cin add[c] del[c];}for (int L 2; L m; L)for (int i 1; i L - 1 m; i) {int j i L - 1;if (s[i] s[j]) f[i][j] f[i 1][j - 1];else f[i][j] min(f[i1][j] min(add[s[i]], del[s[i]]),f[i][j-1] min(add[s[j]], del[s[j]]));}coutreturn 0;}P1279 字串距离题目描述设有字符串X我们称在X的头尾及中间插入任意多个空格后构成的新字符串为X的扩展串如字符串X为”abcbcd”则字符串“abcb□cd”“□a□bcbcd□”和“abcb□cd□”都是X的扩展串这里“□”代表空格字符。如果A1是字符串A的扩展串B1是字符串B的扩展串A1与B1具有相同的长度那么我扪定义字符串A1与B1的距离为相应位置上的字符的距离总和而两个非空格字符的距离定义为它们的ASCII码的差的绝对值而空格字符与其他任意字符之间的距离为已知的定值K空格字符与空格字符的距离为0。在字符串A、B的所有扩展串中必定存在两个等长的扩展串A1、B1使得A1与B1之间的距离达到最小我们将这一距离定义为字符串A、B的距离。请你写一个程序求出字符串A、B的距离。输入输出格式输入格式输入文件第一行为字符串A第二行为字符串B。A、B均由小写字母组成且长度均不超过2000。第三行为一个整数K(1≤K≤100)表示空格与其他字符的距离。输出格式输出文件仅一行包含一个整数表示所求得字符串A、B的距离。输入输出样例输入样例#1cmcsnmn2输出样例#110\(dp[i][j]\)表示第一个串的前i个字符和第二个串的前j个字符的最优值两个空格对应显然没有意义那么有3种转移\(dp[i-1][j]K\)\(dp[i][j-1]K\)\(dp[i-1][j-1]abs(S1[i]-S2[j])\)分别表示S1[i]与空格匹配S2[j]与空格匹配S1[i]与S2[j]匹配。#include #include #include #include #include #include #include #include #include #include using namespace std;const int MAXN 2010;int K;char S1[MAXN], S2[MAXN];int dp[MAXN][MAXN];int clac(int i, int j) {return abs((int) (S1[i] - a) - (int) (S2[j] - a));}int main( ) {scanf(%s%s%d, S1 1, S2 1, K);int len1 strlen(S1 1), len2 strlen(S2 1);memset(dp, 63, sizeof(dp));dp[0][0] 0;for (int i 0; i len1; i)for (int j 0; j len2; j) {if (i) dp[i][j] min(dp[i][j], dp[i - 1][j] K);if (j) dp[i][j] min(dp[i][j], dp[i][j - 1] K);if (i j)dp[i][j] min(dp[i][j], dp[i - 1][j - 1] clac(i, j));}printf(%d\n, dp[len1][len2]);return 0;}caioj 1061: [视频]背包7(匹配性填满型 完全 背包)时间限制: 1 Sec 内存限制: 128 MB【问题描述】判断句子是否可以被划分成若干单词这些单词只可以 “one”、“puton”、“out”、“output”、“in”和“input”。输入n个字符串长度不超过1000000表示一句句子。如果可能是那两个人的对话则输出“YES”否则输出“NO”。【输入文件】第一行一个整数n表示一共有n句句子。此后每行一个字符串表示一句句子。【输出文件】n行每行一个“YES”或“NO”表示你的判断结果。样例输入输出样例输入6putoninonputinoneputonininputoutoutputoneininputwooutoutputoutpuutput样例输出YESNOYESNONONO如果不知道这是一道背包题的话可能没几个人会往背包的方面想。我们不妨把题目中给定的6个单词看做六个数量无限的物品现在他们要装到一个背包中比如要装一个input能装入背包的条件是当前装了一些的背包中再往后需要的字母依次是i,n,p,u,t。最后成功的条件是背包被装满即\(dp[串长]\)有值。\(dp[i]\)表示前i个字符是否能完成匹配。如上所述则dp[i]能由dp[i - len[i]] 推出当且仅当子串c[j - len[i] ~ j] 为给定的单词。单纯这样做还会TLE。可以简单优化一下具体参照代码。#include #include #include #include #include #include #include #include #include #include using namespace std;const int MAXM 1000010;const int MAXN 1010;int n;string c[] {, one, puton, out, output, in, input};int len[] {0, 3, 5, 3, 6, 2, 5};int dp[MAXM];int main( ) {scanf(%d, n);string s; int l;for (int i 1; i n; i) {memset(dp, 0, sizeof(dp));cin s;l s.size( );dp[0] 1;for (int j 1; j l; j)if(s[j - 1] e || s[j - 1] n || s[j - 1] t) //优化for (int i 1; i 6; i)if (j - len[i] 0)if(s[j - len[i]] o || s[j - len[i]] p || s[j - len[i]] i) //优化if (s.substr(j - len[i], len[i]) c[i])dp[j] dp[j] | dp[j - len[i]];if (dp[l]) printf(YES\n);else printf(NO\n);}}P1136 迎接仪式题目描述LHX教主要来X市指导OI学习工作了。为了迎接教主在一条道路旁一群Orz教主er穿着文化衫站在道路两旁迎接教主每件文化衫上都印着大字。一旁的Orzer依次摆出“欢迎欢迎欢迎欢迎……”的大字但是领队突然发现另一旁穿着“教”和“主”字文化衫的Orzer却不太和谐。为了简单描述这个不和谐的队列我们用“j”替代“教”“z”替代“主”。而一个“j”与“z”组成的序列则可以描述当前的队列。为了让教主看得尽量舒服你必须调整队列使得“jz”子串尽量多。每次调整你可以交换任意位置上的两个人也就是序列中任意位置上的两个字母。而因为教主马上就来了时间仅够最多作K次调整(当然可以调整不满K次)所以这个问题交给了你。输入输出格式输入格式第一行包含2个正整数N与K表示了序列长度与最多交换次数。第二行包含了一个长度为N的字符串字符串仅由字母“j”与字母“z”组成描述了这个序列。输出格式一个非负整数为调整最多K次后最后最多能出现多少个“jz”子串。输入输出样例输入样例#15 2zzzjj输出样例#12说明【样例说明】第1次交换位置1上的z和位置4上的j变为jzzzj第2次交换位置4上的z和位置5上的j变为jzzjz。最后的串有2个“jz”子串。【数据规模与约定】对于10%的数据有N≤10对于30%的数据有K≤10对于40%的数据有N≤50对于100%的数据有N≤500,K≤100。一开始不知道怎么做。考虑\(dp[i][j][k]\)表示考虑前i个字符有j个j变成了zk个z变成了j。然后呢然后我就不知道了首先显然两个一样的字符不会被修改。相邻两字符有四种情况可以转移zj jz jj zz。若\(s[i]j ~\\~ s[i-1]z\)\(dp[i][j][k]max(dp[i][j][k],dp[i-2][j][k]1);\)若\(s[i]z ~\\~ s[i-1]j\)\(dp[i][j][k]max(dp[i][j][k],dp[i-2][j-1][k-1]1);\)上面两种情况都比较显然。那么另外两种情况呢若\(s[i]j ~\\~ s[i-1]j\)\(dp[i][j][k]max(dp[i][j][k],dp[i-2][j-1][k]1);\)若\(s[i]z ~\\~ s[i-1]z\)\(dp[i][j][k]max(dp[i][j][k],dp[i-2][j][k-1]1);\)感性理解一下就是我把不合法的变成合法的可以看做当前不合法的与前面或后面某个数交换了一下使之合法但具体是与哪个数交换的我们不需要去知道。因为当交换次数\(jk\)时显然是存在至少一种合法的操作顺序令原字符串可以通过jk次交换变成合法。当交换次数\(j \not k\)时显然不存在这种交换方式那我们就不必去管他。最后对所有的\(dp[N][i][i]\)取max。比较巧妙。顺便注意边界处理。#include #include #include #include #include #include #include #include #include #include #include using namespace std;const int INF 0x3f3f3f3f;const int MAXN 510;const int MAXK 110;int N, K;//dp[i][j][k]表示考虑前i个字符有j个‘j’变成了zk个‘z’变成了jint l[MAXN], dp[MAXN][MAXK][MAXK];char tmp[MAXN];template inline void read(_Tp x) {char ch getchar( ); bool f 0; x 0;while (!isdigit(ch)) { if (ch -) f 1; ch getchar( ); }while (isdigit(ch)) x x * 10 ch - 0, ch getchar( );x f ? -x : x;}int main( ) {memset(dp, ~63, sizeof(dp));read(N), read(K);scanf(%s, tmp 1);for (int i 1; i N; i)if (tmp[i] z) l[i] 1;else l[i] 0;//for (int i 1; i N; i) printf(%d\n, l[i]);dp[0][0][0] dp[1][0][0] dp[1][l[1]][l[1]] 0;for (int i 2; i N; i)for (int j 0; j K; j)for (int k 0; k K; k) {dp[i][j][k] dp[i - 1][j][k];if (!l[i - 1] l[i])dp[i][j][k] max(dp[i][j][k], dp[i - 2][j][k] 1);if (k l[i] l[i - 1])dp[i][j][k] max(dp[i][j][k], dp[i - 2][j][k - 1] 1);if (j !l[i] !l[i - 1])dp[i][j][k] max(dp[i][j][k], dp[i - 2][j - 1][k] 1);if (j k !l[i] l[i - 1])dp[i][j][k] max(dp[i][j][k], dp[i - 2][j - 1][k - 1] 1);}int ans 0;for (int i 0; i K; i) ans max(ans, dp[N][i][i]);printf(%d\n, ans);return 0;}
