uva-10602-貪心

題意：有個編輯器,支持三種操作,摁下一個鍵盤上的字符,重復最后一個單詞,刪除最后一個字符.給N個字符串,必須先在編輯器內輸入第一個字符,

問,輸入完所有字符串最少需要摁下多少次鍵盤.

最多100個字符串,每個字符串長度最多為100.

可以觀察到,為了使摁下鍵盤的次數最少,必須盡可能的利用當前輸入的最后一個字符串.考慮到倆個操作,重復最后一個字符串,刪除最后一個字符,那么,只要前綴是匹配的,就可以通過這

倆個操作來減少摁下鍵盤的次數.所以每次都找前綴匹配最大的字符串即可.

老羅一定做過這個題,而且抄襲了這個創意,用語音控制輸入.

#include <string> #include<iostream> #include<map> #include<memory.h> #include<vector> #include<algorithm> #include<queue> #include<vector> #include<stack> #include<math.h> #include<iomanip> #include<bitset> #include"math.h" namespace cc {using std::cout;using std::endl;using std::cin;using std::map;using std::vector;using std::string;using std::sort;using std::priority_queue;using std::greater;using std::vector;using std::swap;using std::stack;using std::bitset;constexpr int N = 110;int cases;char strs[N][N];char cur[N];int total = 0;int n;void solve(){cin >> cases;while (cases--) {cin >> n;total = 0;memset(strs,0,sizeof(strs));for (int i=0;i<n;i++) {scanf("%s",strs[i]);}total += strlen(strs[0]);memcpy(cur,strs[0],sizeof(strs[0]));int vis[N] = {0};int seqs[N] = {0};int seq = 0;seqs[seq++] = 0;vis[0] = 1;while (true) {int nextIndex = -1;int min = -1;int curL = strlen(cur);for (int i=0;i<n;i++) {if (vis[i] != 0)continue;int curMin = 0;for (int j=0;j< curL;j++){if (strs[i][j] == '\0'|| strs[i][j]!= cur[j])break;++curMin;}if (min < curMin){min = curMin;nextIndex = i;}}if (nextIndex == -1)break;vis[nextIndex] = 1;seqs[seq++] = nextIndex;total += strlen(strs[nextIndex])-min;memcpy(cur,strs[nextIndex],N);}cout << total << endl;for (int i = 0;i < n;i++){cout << strs[seqs[i]] << endl;}}}};int main() {#ifndef ONLINE_JUDGEfreopen("d://1.text", "r", stdin); #endif // !ONLINE_JUDGEcc::solve();return 0; }

?

posted on 2019-01-19 17:02 好吧,就是菜菜 閱讀(...) 評論(...) 編輯 收藏

轉載于:https://www.cnblogs.com/shuiyonglewodezzzzz/p/10292278.html

總結

以上是生活随笔為你收集整理的uva-10602-贪心的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。