「CFgym100486J」 Saving the Universe
he urban legend goes that if you go to the Google homepage
and search for Google, the universe will implode. We have a
secret to share… It is true! Please don’t try it, or tell anyone.
All right, maybe not. We are just kidding
The same is not true for a universe far far away. In that
universe, if you search on any search engine for that search
engine’s name, the universe does implode!
To combat this, people came up with an interesting solution.
All queries are pooled together. They are passed to a central
system that decides which query goes to which search engine.
The central system sends a series of queries to one search
engine, and can switch to another at any time. Queries must
be processed in the order they’re received. The central system
must never send a query to a search engine whose name
matches the query. In order to reduce costs, the number of
switches should be minimized.
Your task is to tell us how many times the central system
will have to switch between search engines, assuming that
we program it optimally.
Input
The rst line of the input le contains the number of cases,
N (1 ≤ N ≤ 20). N test cases follow.
Each case starts with the number S (2 ≤ S ≤ 100) the
number of search engines. The next S lines each contain
the name of a search engine. Each search engine name is no
more than one hundred characters long and contains only
uppercase letters, lowercase letters, spaces, and numbers.
There will not be two search engines with the same name.
The following line contains a number Q (0 ≤ Q ≤ 1000)
the number of incoming queries. The next Q lines will each
contain a query. Each query will be the name of a search
engine in the case.
Output
For each input case, you should output Y , where Y is the
number of search engine switches. Do not count the initial
choice of a search engine as a switch.
Examples
stdin
2
5
Yeehaw
NSM
Dont Ask
B9
Googol
10
Yeehaw
Yeehaw
Googol
B9
Googol
NSM
B9
NSM
Dont Ask
Googol
5
Yeehaw
NSM
Dont Ask
B9
Googol
7
Googol
Dont Ask
NSM
NSM
Yeehaw
Yeehaw
Googol
stdout
1
0
dp，f[i][j]表示前i个关键字的最后一个使用的搜索引擎为j的最小更换次数
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<map> #include<string> #define inf 1000000000 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T,n,m,sz; int mn[1005],f[1005][105]; int a[105],b[1005]; string ch; map<string,int> mp; int main() { T=read(); while(T--) { mp.clear();sz=0; n=read(); for(int i=1;i<=n;i++) { getline(cin,ch); a[i]=mp[ch]=++sz; } m=read(); for(int i=1;i<=m;i++) { getline(cin,ch); b[i]=mp[ch]; } memset(mn,127/3,sizeof(mn)); mn[0]=0; for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) if(b[i]==a[j]) f[i][j]=inf; else { f[i][j]=min(f[i-1][j],mn[i-1]+1); mn[i]=min(mn[i],f[i][j]); } printf("%d\n",mn[m]); } return 0; } |
OI 课件=>
