礼物·动态规划
题目信息
小张的好朋友小松要过生日了，小张打算为他挑选一件礼物。在市场上他发现有一个珠子手镯的商店很不错。在这家商店会出售特殊的珠子并穿成一个手镯，在货架上珠子排成一排，每一个珠子上有一个小写英文字母。店家有一个特殊的规定，必须在一排珠子中按顺序从左到右挑选。小张心中已经有一个想要送给小松的单词，请你告诉他应该如何挑选珠子使得手镯上珠子的字母组成小张想要的单词。
输入
第一行，一个字符串，表示货架上的一排珠子，仅包含小写英文字母，长度在200000以内。
第二行，一个字符串，表示小张想要的单词，仅包含小写英文字母，长度在10000以内。
输出
输出一行整数，表示小张按照从左到右需要挑选的珠子在货架上的位置。
注意
从左到右按顺序选出的珠子上的字母为’p’，‘p’，‘y’，‘h’，‘a’。串成环形的手镯后可以组成"happy"。
数据保证有解，若有多种选取方法，输出其中任意一个。
测试样例
pxrtpsapyjhuvab happy 12
1 5 9 11 14 1
解答
#include <cstring> #include <iostream> using namespace std; string x; string word; int op[200010] = {0}; int lenx; int lenword; int main() { //freopen("E://test.txt", "r", stdin); cin >> x >> word; lenx = x.length(); lenword = word.length(); string words = word + word + word; //cout << words << endl; for (int i = 0; i < lenword; i++) {//用i来循环所有单词的组合 string tmpword(words, i + lenword *5/6, lenword); int k = 0; for (int j = 0; j < lenx; j++) {//用j来循环x中的每一个字符 if (x[j] == tmpword[k]) {//如果存在相同的情况 op[j] = 1;//留下标记 k++; } if (k == lenword) {//找到结果了，因为k长度与单词长度一样了 int r = 0; for (int p = 0; p < lenx; p++) { if (op[p] == 1) { cout << p + 1; if (r < lenword - 1) { cout << " "; } r++; } } cout << endl; return 0; } } memset(op, 0, sizeof(op)); } return 0; } 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354
相关知识
算法（七）100个经典的动态规划方程
【动态规划】摆花
花店橱窗布置（洛谷P1854）（动态规划）
动态规划之摆放花束
[动态规划]花店橱窗布置
摆花 （DP动态规划）
=天津市规划和自然资源局天津市绿色生态屏障动态监测信息更新和
节日礼物,节日送什么礼物？
植物种群动态
城市绿地规划研究论文
网址: 礼物·动态规划 https://m.huajiangbk.com/newsview414515.html
| 上一篇: 如何花光 Microsoft 礼 |
下一篇: 送花草送什么礼物 |
