]]>
|
Time Limit: 1000MS |
|
Memory Limit: 30000K |
|
Total Submissions: 1342 |
|
Accepted: 587 |
Description
Running a taxi station is not all that simple. Apart from the obvious demand for a centralised coordination of the cabs in order to pick up the customers calling to get a cab as soon as possible,there is also a need to schedule all the taxi rides which have been booked in advance.Given a list of all booked taxi rides for the next day, you want to minimise the number of cabs needed to carry out all of the rides.
For the sake of simplicity, we model a city as a rectangular grid. An address in the city is denoted by two integers: the street and avenue number. The time needed to get from the address a, b to c, d by taxi is |a - c| + |b - d| minutes. A cab may carry out a booked ride if it is its first ride of the day, or if it can get to the source address of the new ride from its latest,at least one minute before the new ride's scheduled departure. Note that some rides may end after midnight.
Input
On the first line of the input is a single positive integer N, telling the number of test scenarios to follow. Each scenario begins with a line containing an integer M, 0 < M < 500, being the number of booked taxi rides. The following M lines contain the rides. Each ride is described by a departure time on the format hh:mm (ranging from 00:00 to 23:59), two integers a b that are the coordinates of the source address and two integers c d that are the coordinates of the destination address. All coordinates are at least 0 and strictly smaller than 200. The booked rides in each scenario are sorted in order of increasing departure time.
Output
For each scenario, output one line containing the minimum number of cabs required to carry out all the booked taxi rides.
Sample Input
2
2
08:00 10 11 9 16
08:07 9 16 10 11
2
08:00 10 11 9 16
08:06 9 16 10 11
Sample Output
1
2
Source
鏍規嵁榪欓亾棰樼洰鐨勬剰鎬濓紝鎴戜滑鍙互寤轟竴寮犲浘錛屽浜庝袱涓?/span>booked taxi ride錛?/span>ri鍜?/span>rj濡傛灉涓杈嗚濺鑳藉鍏堝畬鎴?/span>ri鐨勪換鍔″啀鏈夋椂闂磋刀鍘誨畬鎴?/span>rj鐨勪換鍔★紝閭ｄ箞灝卞緩绔嬩竴鏉?/span>ri鎸囧悜rj鐨勮竟銆?br>
鎸夌収棰樼洰鐨勮姹傦紝瑕侀夋嫨鏈灝戠殑taxi鏉ュ畬鎴愯繖浜涗換鍔°傛樉鐒跺湪涓婇潰榪欎釜渚嬪瓙涓紝闇瑕佸畨鎺?/span>2杈?/span>taxi銆傜粨鍚堣繖涓浘錛屽彲浠ユ妸棰樼洰鐨勮姹傝漿鍖栦負鎵懼嚭鏈灝戠殑璺緞鏉℃暟錛屼嬌寰楄繖浜涜礬寰勮鐩栭斾腑鎵鏈夌殑杈癸紝渚嬪鍙互閫夋嫨2鏉¤礬寰?/span>1->3->4鍜?/span>1->2灝卞彲浠ヨ鐩栨墍鏈夌殑杈廣備篃鍙互閫夋嫨1->3->4鍜?/span>2錛堝洜涓?/span>2浣滀負鍒濆绔欙紝涓嶉渶瑕佺敱1杞Щ榪囨潵錛夈傚浜庝竴鏉¤繛緇殑璺緞vi1->vi2->…vik鐢變簬榪欐潯璺緞涓婄殑浠誨姟瀹為檯涓婃槸鐢變竴杈?/span>taxi鏉ュ畬鎴愮殑錛屽彲浠ュ惂榪欐潯璺緞閫鍖栨垚涓や釜鐐?/span>vi1->vik銆傛湁浜嗚繖涓ゆ寤哄浘鐨勬楠や互鍚庯紝闂鐨勬眰瑙ｅ氨鍙互鍙樹負鎵懼嚭欏剁偣闆嗙殑涓涓渶灝忓瓙闆嗭紝浣胯繖涓《鐐瑰瓙闆嗚鐩栨墍鏈夌殑杈癸紙姣忔潯杈歸兘鑷沖皯鍜屼竴涓《鐐歸泦鐨勯《鐐圭浉榪烇級銆傝繖涓棶棰樺氨鏄浘鐨勬渶灝忕偣瑕嗙洊銆傚啀鐪嬭繖寮犲浘錛岃繕鏈変竴浜涙ц川鑳藉璁╂垜浠洿濂藉湴姹傚嚭鏈灝忕偣瑕嗙洊銆傝繖涓浘鏄竴涓湁鍚戞棤鐜浘錛屾病鏈夎嚜鐜紝灝卞彲浠ユ媶鐐癸紝鎶婂師鍏堝緩鐨勫浘鍙樻垚涓寮犱簩鍒嗗浘銆?br>
鍙互鍐嶅浘涓湅鍑猴紝涓婇潰涓懼嚭鐨勪竴鏉¤礬寰?/span>1->3->4瀵瑰簲浜嗚繖涓簩鍒嗗浘涓殑璺緞1->
1
#include <stdio.h>2
#include <string.h>3
#include <algorithm>4
using namespace std;5
6
struct Point7
{8
int x,y;9
};10
struct P11
{12
int s,e;13
struct Point s1,s2;14
}p[505];15
int n,g[505][505],match[505];16
bool chk[505];17
18
/**//*int abs(int a)19
{20
return a < 0 ? -a : a;21
}*/22
bool operator <(const P a, const P b)23
{24
return a.s < b.s;25
}26
int dfs(int v)27
{28
int i,t;29
for(i=0; i<n; i++)30
{31
if(!chk[i] && g[v][i])32
{33
t=match[i];34
chk[i]=true;35
match[i]=v;36
if(t == -1 || dfs(t)) return 1;37
match[i]=t;38
}39
}40
return 0;41
}42
int Twomatch()43
{44
int i,ans=0;45
memset(match,-1,sizeof(match));46
for(i=0; i<n; i++)47
{48
memset(chk,false,sizeof(chk));49
if(dfs(i)) ans++;50
}51
return ans;52
}53
54
int main()55
{56
int i,cases,a,b,j,cnt;57
char temp[10];58
//freopen("in.txt","r",stdin);59
scanf("%d",&cases);60
while(cases--)61
{62
scanf("%d",&n);63
64
for(i=0; i<n; i++)65
{66
scanf("%s",temp);67
scanf("%d%d%d%d",&p[i].s1.x,&p[i].s1.y,&p[i].s2.x,&p[i].s2.y);68
sscanf(temp,"%d%*[:]%d",&a,&b);69
p[i].s=a*60+b;70
p[i].e=p[i].s+abs(p[i].s2.x-p[i].s1.x)+abs(p[i].s2.y-p[i].s1.y);71
}72
//sort(p,p+n);73
cnt=0;74
memset(g,0,sizeof(g));75
for(i=0; i<n; i++)76
{77
for(j=0; j<n; j++)78
{79
if(p[i].e+abs(p[i].s2.x-p[j].s1.x)+abs(p[i].s2.y-p[j].s1.y) < p[j].s && i != j)80
g[i][j]=1;81
}82
}83
printf("%d\n",n-Twomatch());84
}85
return 0;86
}87
]]>
]]>
| Time Limit: 1000MS | Memory Limit: 30000K | |
| Total Submissions: 574 | Accepted: 229 |
Description
You are appointed director of a famous concert hall, to save it from bankruptcy. The hall is very popular, and receives many requests to use its two fine rooms, but unfortunately the previous director was not very efficient, and it has been losing money for many years. The two rooms are of the same size and arrangement. Therefore, each applicant wishing to hold a concert asks for a room without specifying which. Each room can be used for only one concert per day.
In order to make more money, you have decided to abandon the previous fixed price policy, and rather let applicants specify the price they are ready to pay. Each application shall specify a period [i, j] and an asking price w, where i and j are respectively the first and last days of the period (1 <= i <= j <= 365), and w is a positive integer in yen, indicating the amount the applicant is willing to pay to use a room for the whole period.
You have received applications for the next year, and you should now choose the applications you will accept. Each application should be either accepted for its whole period or completely rejected. Each concert should use the same room during the whole applied period.
Considering the dire economic situation of the concert hall, artistic quality is to be ignored, and you should just try to maximize the total income for the whole year by accepting the most profitable applications.
In order to make more money, you have decided to abandon the previous fixed price policy, and rather let applicants specify the price they are ready to pay. Each application shall specify a period [i, j] and an asking price w, where i and j are respectively the first and last days of the period (1 <= i <= j <= 365), and w is a positive integer in yen, indicating the amount the applicant is willing to pay to use a room for the whole period.
You have received applications for the next year, and you should now choose the applications you will accept. Each application should be either accepted for its whole period or completely rejected. Each concert should use the same room during the whole applied period.
Considering the dire economic situation of the concert hall, artistic quality is to be ignored, and you should just try to maximize the total income for the whole year by accepting the most profitable applications.
Input
The input has multiple data sets, each starting with a line consisting of a single integer n, the number of applications in the data set. Then, it is followed by n lines, each of which represents one application with a period [i, j] and an asking price w yen in the following format.
i j w
A line containing a single zero indicates the end of the input.
The maximum number of applications in a data set is one thousand, and the maximum asking price is one million yen.
i j w
A line containing a single zero indicates the end of the input.
The maximum number of applications in a data set is one thousand, and the maximum asking price is one million yen.
Output
For each data set, print a single line containing an integer, the maximum total income in yen for the data set.
Sample Input
4 1 2 10 2 3 10 3 3 10 1 3 10 6 1 20 1000 3 25 10000 5 15 5000 22 300 5500 10 295 9000 7 7 6000 8 32 251 2261 123 281 1339 211 235 5641 162 217 7273 22 139 7851 194 198 9190 119 274 878 122 173 8640 0
Sample Output
30 25500 38595
Source
Japan 2003,Aizu
榪欓亾棰樼洰鏀句簡寰堜箙浜嗭紝涓鐩存病鎯沖嚭濂界殑瑙ｆ硶銆傛渶榪戠殑鍑犳姣旇禌涓兘閬囧埌浜嗚繖閬撻錛屾瘮璧涘悗鎵嶆妸榪欓鎼炲畾銆傝繖棰樼殑鏂規硶鏄疍P銆傝緭鍏ユ暟鎹褰曡澶勭悊涓涓嬶紝寮涓涓?66澶х殑vector鏁扮粍錛岃褰曚簡鍒扮e澶╃粨鏉熸椂鐨勯煶涔愪細鐨勫紑濮嬫椂闂磗鍜屾敹鐩妛銆傚紑涓涓猟p[366][366]鐨勬暟緇勶紝鍏朵腑dp[i][j]琛ㄧず絎竴涓煶涔愬巺鍦ㄧi澶╋紝絎簩涓煶涔愬巺鍦ㄧj澶╂敹鍒扮殑yen銆傚洜涓洪瀹氱殑闊充箰浼氬崰鐢ㄩ煶涔愬巺鏄湁涓涓尯闂寸殑錛岃繖閲屽仛涓涓鐞嗭紝灝辨槸鍦ㄤ竴鍦洪煶涔愪細鍗犵敤鐨勬湡闂撮兘涓嶆敹閽憋紝鐩村埌涓涓煶涔愪細瀹屽叏緇撴潫鍚庢墠鏀墮挶銆傚彟澶栦袱涓煶涔愬巺鏄竴鏍風殑錛屽嵆鏈鍚巇p[i][j]搴旇鏄竴涓縐版暟緇勶紝褰撳彧鎺ュ彈涓鍦洪煶涔愪細鐨勬儏鍐靛彲浠ュ己琛岀殑璁や負榪欏満闊充箰浼氭槸鏀懼湪絎竴涓煶涔愬巺錛岃綆梔p[i][j]涓墍鏈塱>j鐨勫鹼紝鏈鍚庡啀浠p[j][i]=dp[i][j]鍗沖彲銆?br>
1for(i=1; i<=365; i++)
2 {
3 for(jj=0; jj<hall[i].size(); jj++)
4 {
5 for(j=0; j<i; j++)
6 {
7 dp[i][j]=Max(dp[i][j],dp[hall[i][jj].s-1][j]+hall[i][jj].w);
8 }
9 for(ii=jj+1; ii<hall[i].size(); ii++)
10 {
11 dp[i][i]=Max(dp[i][i],dp[hall[i][jj].s-1][hall[i][ii].s-1]+
12 hall[i][jj].w+hall[i][ii].w);
13 }
14 }
15 for(j=1; j<=i; j++)
16 {
17 dp[i][j]=Max(dp[i-1][j],dp[i][j]);
18 dp[i][j]=Max(dp[i][j-1],dp[i][j]);
19 dp[j][i]=dp[i][j];
20 }
21 }
for(i=1; i<=365; i++)2
{3
for(jj=0; jj<hall[i].size(); jj++)4
{5
for(j=0; j<i; j++)6
{7
dp[i][j]=Max(dp[i][j],dp[hall[i][jj].s-1][j]+hall[i][jj].w);8
}9
for(ii=jj+1; ii<hall[i].size(); ii++)10
{11
dp[i][i]=Max(dp[i][i],dp[hall[i][jj].s-1][hall[i][ii].s-1]+12
hall[i][jj].w+hall[i][ii].w);13
}14
}15
for(j=1; j<=i; j++)16
{17
dp[i][j]=Max(dp[i-1][j],dp[i][j]);18
dp[i][j]=Max(dp[i][j-1],dp[i][j]);19
dp[j][i]=dp[i][j];20
}21
}]]>
]]>
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 211 | Accepted: 82 |
Description
The Archaeologists of the Current Millenium (ACM) now and then discover ancient artifacts located at the vertices of regular polygons. In general it is necessary to move one sand dune to uncover each artifact. After discovering three artifacts, the archaeologists wish to compute the minimum number of dunes that must be moved to uncover all of them.
Input
The first line of input contains a positive integer n, the number of test cases. Each test case consists of three pairs of real numbers giving the x and y coordinates of three vertices from a regular polygon.
Output
For each line of input, output a single integer stating the fewest vertices that such a polygon might have. You may assume that each input case gives three distinct vertices of a regular polygon with at most 200 vertices.
Sample Input
4 10.00000 0.00000 0.00000 -10.00000 -10.00000 0.00000 22.23086 0.42320 -4.87328 11.92822 1.76914 27.57680 156.71567 -13.63236 139.03195 -22.04236 137.96925 -11.70517 129.400249 -44.695226 122.278798 -53.696996 44.828427 -83.507917
Sample Output
4 6 23 100
Source
棰樼洰澶ф剰鏄粰鍑轟笁涓偣鐨?x,y)鍧愭爣錛岃姹傝緭鍑轟竴涓竟鏁版渶灝忕殑姝ｅ杈瑰艦鐨勮竟鏁幫紝浣胯繖涓変釜鐐規伆濂藉湪
榪欎釜姝ｅ杈瑰艦涓婇潰銆傚叾瀹炶繖涓笁瑙掑艦鍜岃繖涓澶氳竟褰㈡槸鍏卞鎺ュ渾錛岀敱澶栨帴鍦嗙殑鍦嗗績鍑哄彂錛屼笁瑙掑艦鐨勪笁
鏉¤竟鍙互鎶婂渾鍒嗘垚涓変喚錛屾瘡浠藉渾寮ф墍瀵瑰簲鐨勫渾蹇冭鍒嗗埆涓篴rg[0],arg[1]鍜宎rg[2]錛屾澶氳竟褰㈡妸鍦嗗姬
鍒嗘垚鐩哥瓑鐨刵浠斤紝姣忎喚瀵瑰簲鐨勫渾蹇冭涓?*pi/n銆傚叾瀹炰笁瑙掑艦鐨勪笁涓灝卞垎鍒崰鐢ㄤ簡鑻ュ共絳変喚姝ｅ杈瑰艦
鎵鍒掑垎鐨勫渾寮э紝鏈鍚庝篃灝卞彧瑕佹眰arg[0],arg[1],arg[2]鍜?*pi鐨勬渶澶у叕綰︽暟(gcd)鍗沖彲銆備絾鏄繖閲屾槸
涓搴﹂兘鏄誕鐐規暟錛屾墍浠ヨ繕瀹氫箟涓涓誕鐐規暟鐨刧cd錛岃綆楁誕鐐規暟鐨刧cd鍙互鍒╃敤math.h鐨勫嚱鏁癴mod
(x,y)琛ㄧずx%y銆備緥濡?.5%0.3=0.2錛寈%y鐨勭粨鏋滀負涓嶈秴榪噛鐨勪竴涓誕鐐規暟銆備笅闈㈠啓浜嗕竴涓猣mod(x,y)鑷繁
鐨勫疄鐜般?br>double fmod(double x, double y)
{
return x-floor(x/y)*y;
}
鏈変簡fmod鍑芥暟浠ュ悗錛屽氨鍙互鐢ㄥ畠鏉ユ眰gcd浜嗭紒
double fgcd(double a, double b)
{
double t;
if(dblcmp(a-b) == 1) //a>b
{
t=a;
a=b;
b=t;
}
if(dblcmp(a) == 0) return b;
return fgcd(fmod(b,a),a);
}
]]>
]]>