首页 > ACM题库 > HDU-杭电 > hdu 2557 Jumping the Queue -动态规划-[解题报告]other
2014
02-10

hdu 2557 Jumping the Queue -动态规划-[解题报告]other

Jumping the Queue

问题描述 :

The beginning of a winter break near Spring Festival is always the beginning of a peak period of transportation. If you have ever tried to get a train ticket at that time, you must have witnessed the endless queues in front of every ticket box window. If a guy has seen his friend in a queue, then it is very much likely that this lucky guy might go straight to his friend and ask for a favor. This is called "jumping the queue". It is unfair to the rest of the people in the line, but, it is life. Your task is to write a program that simulates such a queue with people jumping in every now and then, assume that, if one in the queue has several friends asking for favors, he would arrange their requests in a queue of his own.

输入:

There will contain one or more test cases. Each test case begins with the number of groups n (1<= n <=1000). Then n group descriptions follow, each one consisting of the number of friends belonging to the group and those people’s distinct names. A group is a friend group. People in one group are friend with each other. A name is a string of up to 4 characters chosen from {A, B, …, Z, a, b, …, z}. A group may consist of up to 1000 friends. You may assume that there is no one belong to two different groups.
Finally, a list of commands follows. There are three different kinds of commands:

ENQUEUE X – Mr. or Ms. X goes into the queue
DEQUEUE – the first person gets the ticket and leave the queue
STOP – end of test case

The input will be terminated by a value of 0 for n.

输出:

There will contain one or more test cases. Each test case begins with the number of groups n (1<= n <=1000). Then n group descriptions follow, each one consisting of the number of friends belonging to the group and those people’s distinct names. A group is a friend group. People in one group are friend with each other. A name is a string of up to 4 characters chosen from {A, B, …, Z, a, b, …, z}. A group may consist of up to 1000 friends. You may assume that there is no one belong to two different groups.
Finally, a list of commands follows. There are three different kinds of commands:

ENQUEUE X – Mr. or Ms. X goes into the queue
DEQUEUE – the first person gets the ticket and leave the queue
STOP – end of test case

The input will be terminated by a value of 0 for n.

样例输入:

2
3 Ann Bob Joe
3 Zoe Jim Fat
ENQUEUE Ann
ENQUEUE Zoe
ENQUEUE Bob
ENQUEUE Jim
ENQUEUE Joe
ENQUEUE Fat
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
2
5 Anny Jack Jean Bill Jane
6 Eva Mike Ron Sony Geo Zoro
ENQUEUE Anny
ENQUEUE Eva
ENQUEUE Jack
ENQUEUE Jean
ENQUEUE Bill
ENQUEUE Jane
DEQUEUE
DEQUEUE
ENQUEUE Mike
ENQUEUE Ron
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP 
0

样例输出:

Scenario #1 
Ann
Bob
Joe
Zoe
Jim
Fat

Scenario #2 
Anny
Jack
Jean
Bill
Jane
Eva

Hint
You must maintain a hash table to store the names of the people, otherwise the efficiency of your program will not be acceptable since Judge's input file is as large as about 12.5MB.

 

题意:给你一串字符串,只包含大写字母和小写字母,问打出这串字符最少要按多少次键。但如果Caps Lock键最后是打开的一定要把Caps Lock键关掉。

 

题解:首先你要知道1.当Caps Lock键关闭的时候打出一个大写字母可以有两种方法:1.按下Caps Lock键再按字母键 2.按Shift键并按字母键。2.当Caps Lock键打开的时候打出一个小写字母也有两种方法:1.按下Caps Lock键,再按字母键 2.按Shift键并按字母键。

         题目涉及Caps Lock键的两种状态:关闭和打开。因此可以开一个二维数组,一维表示Caps Lock键关闭,另一维表示Caps Lock键打开。但这里也可以开两个一维数组on[]和off[]分别表示Caps Lock键的两种状态。(此题和算法导论的动态规划章节中的一题双线作业调度类似,那一题也是这样的做法)

状态转移方程:

if(s[i]>='A'&&s[i]<='Z') {//如果是大写字母
                 on[i]=min(on[i-1],off[i-1]+1)+1;//从on状态转移到on状态不需要按任何键,直接按字母键即可,从off状态转移到on状态的最少步数是:先按Caps Lock键再按字母键,所以是off[i-1]+1+1;
                 off[i]=min(on[i-1]+1,off[i-1]+1)+1;//同理~~~
             }
             else {//如果是小写字母
                 on[i]=min(on[i-1]+1,off[i-1]+1)+1;//在这种情况下从on状态转移到on状态的最小步数是先按Shift键并按字母键,从off状态转移到on状态的最小步数是先按字母键再按Caps Lock键,所以是off[i-1]+1+1;
                 off[i]=min(on[i-1]+1,off[i-1])+1;
             }

 

AC代码:

#include<iostream>
 #include<cmath>
 #include<cstring>
 #include<algorithm>
 using namespace std;
 const int N=105;
 int on[N],off[N];
 char s[N];
 int main()
 {
     int T,len;
     cin>>T;
     while(T--){
         cin>>s;
         len=strlen(s);
         if(s[0]>='A'&&s[0]<='Z'){
             on[0]=2;off[0]=2;
         }
         else{
             on[0]=2;off[0]=1;
         }
         for(int i=1;i<len;i++){
             if(s[i]>='A'&&s[i]<='Z') {
                 on[i]=min(on[i-1],off[i-1]+1)+1;
                 off[i]=min(on[i-1]+1,off[i-1]+1)+1;
             }
             else {
                 on[i]=min(on[i-1]+1,off[i-1]+1)+1;
                 off[i]=min(on[i-1]+1,off[i-1])+1;
             }
         }
         cout<<min(on[len-1]+1,off[len-1])<<endl;
     }
     return 0;
 }

 

 

 

解题转自:http://www.cnblogs.com/acmer-roney/archive/2012/09/21/2697075.html


  1. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。