java字符串匹配dp_[OI]字符串DP小结
顧名又思義，是在字符串上進(jìn)行的DP操作。因?yàn)樽址旧砜梢钥醋魇且粋€(gè)序列，所以有些時(shí)候字符串DP可以用區(qū)間DP來(lái)解決。
P2246 SAC#1 - Hello World(升級(jí)版)
題目描述
在講義的某一面，他看見(jiàn)了一篇文章。這篇文章由英文字母(大小寫(xiě)均有)、數(shù)字、和空白字符(制表/空格/回車(chē))構(gòu)成。
pipapi想起了他最近剛剛學(xué)會(huì)寫(xiě)的Hello World程序。他非常好奇，這篇文章中，“HelloWorld”作為子序列到底出現(xiàn)過(guò)多少次呢？
由于papapi是個(gè)智障，大小寫(xiě)對(duì)于他而言毫無(wú)區(qū)別；因此，“hEllOWorLD”這樣的子序列也是可以接受的。O和W之間的空格是也是可以少的；也就是說(shuō)，“HelloWorld”是可以的。根據(jù)標(biāo)程的意思，就是沒(méi)有空格，不用考慮空格的情況。
兩個(gè)子序列相同當(dāng)且僅當(dāng)它們每一個(gè)字符所在的位置都相同。
由于答案可能很大，請(qǐng)輸出結(jié)果對(duì)1000000007(10^9+7)的余數(shù)。
輸入輸出格式
輸入格式：
輸入包含若干行。這些行的內(nèi)容共同構(gòu)成一篇文章。
文章以EOF(文件結(jié)尾)結(jié)束。
輸出格式：
輸出僅包含一個(gè)整數(shù)，表示這篇文章中“Hello World”出現(xiàn)的次數(shù)。 d
輸入輸出樣例
輸入樣例#1：
HhEeLlLlOoWwOoRrLlDd
輸出樣例#1：
1536
輸入樣例#2：
Gou Li Guo Jia Sheng Si Yi
Qi Yin Huo Fu Bi Qu Zhi
River can feed people
Also can race boats
Hall Ellen Ok Words locked
輸出樣例#2：
273
說(shuō)明
記n為輸入的文章的長(zhǎng)度(字符數(shù))。
對(duì)于20%的數(shù)據(jù)，n <= 20。
對(duì)于50%的數(shù)據(jù)，n <= 500。
對(duì)于所有的數(shù)據(jù)，15 <= n <= 500000。
入門(mén)題。設(shè)\(dp[i][j]\)表示文本串前i個(gè)字符匹配helloworld模板的前j個(gè)字符的匹配數(shù)。顯然當(dāng)\(a[i]=b[j]\)時(shí)有\(zhòng)(dp[i][j]=dp[i-1][j-1] + dp[i-1][j]\),其他情況\(dp[i][j]=dp[i-1][j]\)。前面一維直接滾動(dòng)優(yōu)化掉。
#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 tag's 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 cows's 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 cow's ID tag and the cost of inserting or deleting each of the alphabet's characters, find the minimum cost to change the ID tag so it satisfies FJ's 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長(zhǎng)M，由N個(gè)小寫(xiě)字母構(gòu)成。欲通過(guò)增刪字母將其變?yōu)榛匚拇?#xff0c;增刪特定字母花費(fèi)不同，求最小花費(fèi)。
輸入輸出格式
輸入格式：
Line 1: Two space-separated integers: N and M
Line 2: This line contains exactly M characters which constitute the initial ID string
Lines 3..N+2: 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.
輸入輸出樣例
輸入樣例#1：
3 4
abcb
a 1000 1100
b 350 700
c 200 800
輸出樣例#1：
900
說(shuō)明
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.
比較經(jīng)典的字符串DP了。設(shè)\(dp[i][j]\)表示區(qū)間[i,j]變成回文串的最小花費(fèi)，需要用到區(qū)間DP的思想。考慮如何用一個(gè)小區(qū)間更新一個(gè)大區(qū)間。如果大區(qū)間是\(dp[i][j]\)，若s[i]=s[j]，那么\(dp[i][j]=dp[i+1][j-1]\)，即當(dāng)前大區(qū)間可以由去掉其兩端的小區(qū)間更新而來(lái)而不用花費(fèi)。不等的時(shí)候，\(dp[i][j]=min(dp[i+1][j]+min(add[s[i]],del[s[i]]),dp[i][j-1]+min(add[s[j],del[s[j]]])\)
#include
#include
using 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, (s+1));
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[i+1][j] + min(add[s[i]], del[s[i]]),
f[i][j-1] + min(add[s[j]], del[s[j]]));
}
cout<
return 0;
}
P1279 字串距離
題目描述
設(shè)有字符串X，我們稱在X的頭尾及中間插入任意多個(gè)空格后構(gòu)成的新字符串為X的擴(kuò)展串，如字符串X為”abcbcd”，則字符串“abcb□cd”，“□a□bcbcd□”和“abcb□cd□”都是X的擴(kuò)展串，這里“□”代表空格字符。
如果A1是字符串A的擴(kuò)展串，B1是字符串B的擴(kuò)展串，A1與B1具有相同的長(zhǎng)度，那么我捫定義字符串A1與B1的距離為相應(yīng)位置上的字符的距離總和，而兩個(gè)非空格字符的距離定義為它們的ASCII碼的差的絕對(duì)值，而空格字符與其他任意字符之間的距離為已知的定值K，空格字符與空格字符的距離為0。在字符串A、B的所有擴(kuò)展串中，必定存在兩個(gè)等長(zhǎng)的擴(kuò)展串A1、B1，使得A1與B1之間的距離達(dá)到最小，我們將這一距離定義為字符串A、B的距離。
請(qǐng)你寫(xiě)一個(gè)程序，求出字符串A、B的距離。
輸入輸出格式
輸入格式：
輸入文件第一行為字符串A，第二行為字符串B。A、B均由小寫(xiě)字母組成且長(zhǎng)度均不超過(guò)2000。第三行為一個(gè)整數(shù)K(1≤K≤100)，表示空格與其他字符的距離。
輸出格式：
輸出文件僅一行包含一個(gè)整數(shù)，表示所求得字符串A、B的距離。
輸入輸出樣例
輸入樣例#1
cmc
snmn
2
輸出樣例#1：
10
\(dp[i][j]\)表示第一個(gè)串的前i個(gè)字符和第二個(gè)串的前j個(gè)字符的最優(yōu)值，兩個(gè)空格對(duì)應(yīng)顯然沒(méi)有意義，那么有3種轉(zhuǎn)移：\(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(匹配性填滿型 完全 背包)
時(shí)間限制: 1 Sec 內(nèi)存限制: 128 MB
【問(wèn)題描述】
判斷句子是否可以被劃分成若干單詞，這些單詞只可以 “one”、“puton”、“out”、“output”、“in”和“input”。
輸入n個(gè)字符串，長(zhǎng)度不超過(guò)1000000，表示一句句子。
如果可能是那兩個(gè)人的對(duì)話，則輸出“YES”；否則，輸出“NO”。
【輸入文件】
第一行一個(gè)整數(shù)n，表示一共有n句句子。
此后每行一個(gè)字符串，表示一句句子。
【輸出文件】
n行，每行一個(gè)“YES”或“NO”，表示你的判斷結(jié)果。
樣例輸入輸出
樣例輸入
6
puton
inonputin
oneputonininputoutoutput
oneininputwooutoutput
outpu
utput
樣例輸出
YES
NO
YES
NO
NO
NO
如果不知道這是一道背包題的話，可能沒(méi)幾個(gè)人會(huì)往背包的方面想。我們不妨把題目中給定的6個(gè)單詞看做六個(gè)數(shù)量無(wú)限的物品，現(xiàn)在他們要裝到一個(gè)背包中，比如要裝一個(gè)input，能裝入背包的條件是當(dāng)前裝了一些的背包中，再往后需要的字母依次是i,n,p,u,t。最后成功的條件是背包被裝滿，即\(dp[串長(zhǎng)]\)有值。\(dp[i]\)表示前i個(gè)字符是否能完成匹配。如上所述，則dp[i]能由dp[i - len[i]] 推出，當(dāng)且僅當(dāng)，子串c[j - len[i] ~ j] 為給定的單詞。
單純這樣做還會(huì)TLE?？梢院?jiǎn)單優(yōu)化一下，具體參照代碼。
#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') //優(yōu)化
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') //優(yōu)化
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教主要來(lái)X市指導(dǎo)OI學(xué)習(xí)工作了。為了迎接教主，在一條道路旁，一群Orz教主er穿著文化衫站在道路兩旁迎接教主，每件文化衫上都印著大字。一旁的Orzer依次擺出“歡迎歡迎歡迎歡迎……”的大字，但是領(lǐng)隊(duì)突然發(fā)現(xiàn)，另一旁穿著“教”和“主”字文化衫的Orzer卻不太和諧。
為了簡(jiǎn)單描述這個(gè)不和諧的隊(duì)列，我們用“j”替代“教”，“z”替代“主”。而一個(gè)“j”與“z”組成的序列則可以描述當(dāng)前的隊(duì)列。為了讓教主看得盡量舒服，你必須調(diào)整隊(duì)列，使得“jz”子串盡量多。每次調(diào)整你可以交換任意位置上的兩個(gè)人，也就是序列中任意位置上的兩個(gè)字母。而因?yàn)榻讨黢R上就來(lái)了，時(shí)間僅夠最多作K次調(diào)整(當(dāng)然可以調(diào)整不滿K次)，所以這個(gè)問(wèn)題交給了你。
輸入輸出格式
輸入格式：
第一行包含2個(gè)正整數(shù)N與K，表示了序列長(zhǎng)度與最多交換次數(shù)。
第二行包含了一個(gè)長(zhǎng)度為N的字符串，字符串僅由字母“j”與字母“z”組成，描述了這個(gè)序列。
輸出格式：
一個(gè)非負(fù)整數(shù)，為調(diào)整最多K次后最后最多能出現(xiàn)多少個(gè)“jz”子串。
輸入輸出樣例
輸入樣例#1：
5 2
zzzjj
輸出樣例#1：
2
說(shuō)明
【樣例說(shuō)明】
第1次交換位置1上的z和位置4上的j，變?yōu)閖zzzj；
第2次交換位置4上的z和位置5上的j，變?yōu)閖zzjz。
最后的串有2個(gè)“jz”子串。
【數(shù)據(jù)規(guī)模與約定】
對(duì)于10%的數(shù)據(jù)，有N≤10；
對(duì)于30%的數(shù)據(jù)，有K≤10；
對(duì)于40%的數(shù)據(jù)，有N≤50；
對(duì)于100%的數(shù)據(jù)，有N≤500,K≤100。
一開(kāi)始不知道怎么做。考慮\(dp[i][j][k]\)表示考慮前i個(gè)字符，有j個(gè)j變成了z，k個(gè)z變成了j。
然后呢？
然后我就不知道了
首先顯然兩個(gè)一樣的字符不會(huì)被修改。
相鄰兩字符有四種情況可以轉(zhuǎn)移：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);\)
感性理解一下就是，我把不合法的變成合法的，可以看做當(dāng)前不合法的與前面或后面某個(gè)數(shù)交換了一下，使之合法，但具體是與哪個(gè)數(shù)交換的，我們不需要去知道。因?yàn)楫?dāng)交換次數(shù)\(j=k\)時(shí)，顯然是存在至少一種合法的操作順序，令原字符串可以通過(guò)j=k次交換變成合法。當(dāng)交換次數(shù)\(j \not= k\)時(shí)，顯然不存在這種交換方式，那我們就不必去管他。
最后對(duì)所有的\(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個(gè)字符，有j個(gè)‘j’變成了z，k個(gè)‘z’變成了j
int 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;
}
總結(jié)
以上是生活随笔為你收集整理的java字符串匹配dp_[OI]字符串DP小结的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： ntr模式_ntr什么意思？
- 下一篇： linux vim tag,Vim基础知