2011年3月24日
2009年11月27日
Lost Cows
| Time Limit: 1000MS |
|
Memory Limit: 65536K |
| Total Submissions: 4143 |
|
Accepted: 2575 |
Description
N (2 <= N <= 8,000) cows have unique brands in the range 1..N. In a spectacular display of poor judgment, they visited the neighborhood 'watering hole' and drank a few too many beers before dinner. When it was time to line up for their evening meal, they did not line up in the required ascending numerical order of their brands.
Regrettably, FJ does not have a way to sort them. Furthermore, he's not very good at observing problems. Instead of writing down each cow's brand, he determined a rather silly statistic: For each cow in line, he knows the number of cows that precede that cow in line that do, in fact, have smaller brands than that cow.
Given this data, tell FJ the exact ordering of the cows.
Input
* Line 1: A single integer, N
* Lines 2..N: These N-1 lines describe the number of cows that precede a given cow in line and have brands smaller than that cow. Of course, no cows precede the first cow in line, so she is not listed. Line 2 of the input describes the number of preceding cows whose brands are smaller than the cow in slot #2; line 3 describes the number of preceding cows whose brands are smaller than the cow in slot #3; and so on.
Output
* Lines 1..N: Each of the N lines of output tells the brand of a cow in line. Line #1 of the output tells the brand of the first cow in line; line 2 tells the brand of the second cow; and so on.
Sample Input
5
1
2
1
0
Sample Output
2
4
5
3
1
Source
基本思路：
求一个从1-n的整数的序列，满足题目所给的要求。题目给出了n-1个ai的值，ai=m表示在第i（1<i<=n）个数的前面有m个数比第i个数小。我们要求的就是这第i个数是多少。所以只能从后往前找，因为在要求的序列中n个数必须且只能出现一次。然后就不断的查找，删除，最后求出整个序列。 数据，n=
5
0
2
2
1
首先从最后一个开始，表示第5个数前面有一个数小于它，所以这个数一定是2（因为每个数都要出现），然后是倒数第二个 ，表示第4个数字前面有2个数字小于第四个数，说明这个数字是在剩下的数字（除去这个数字以后的所有数字）里的名次排在第3（有两个比他小）。所以类推，从最后个数字开始，求出一个删除一个，第i个要求的数字就是当前所有（i个，前面已经找到了的删除掉）数字排在第ai+1的数字。
显然，如果直接查找然后删除是可以完成的，但是时间复杂度为O（n^2），而题目是数据很大（n<8000），显然要超时。所以需要改进，不要整体操作，用线段数是很好的方法，可以将复杂读降低到O(n*log n).具体如下：
1
#include<iostream>
2using namespace std;
3int k,bj;
4struct stu
5
{
6
int len,rig; //len为左儿子，rig右儿子
7 int s; //表示有多少个数字
8
}a[30000];
9void Lost(int n) //建立线段树Lost，其实是一个中根遍历二叉树
10{ //先遍历根结点，然后遍历左结点，最后遍历右结点
11 k++;
12 int j=k;
13 a[j].s=n;
14 if(n==1) //当n=1的时候说明只有一个数，
15
{
16 a[j].len=bj++; //用此结点的左儿子表示这个
17 a[j].rig=-1; // 并用右儿子rig=-1作标记；
18 return ;
19
}
20 int i;
21 i=n/2;
22 a[j].len=k+1;
23 Lost(i);
24 a[j].rig=k+1;
25 Lost(n-i);
26}
27void Delete(int i,int n) //删除过程，其实也是一个查找过程，具有两个功能 ：
28{ // 查找和删除要求的点结点
29 a[i].s--; //相当于删除一个点，所以总数减少1
30 if(a[i].rig==-1) // gig=-1说明到了叶子结点，查找完成
31 {
32 bj=a[i].len;
33 return ;
34 }
35 int j=a[i].len;
36 if(n<=a[j].s)
37 {
38 Delete(j,n);
39 return ;
40 }
41 else Delete(a[i].rig,n-a[j].s);
42}
43int main()
44{
45 int n,i;
46 int num1[8010],num2[8010];
47 while(scanf("%d",&n)!=EOF)
48 {
49 k=-1;bj=1;
50 Lost(n);
51 num2[0]=0;
52 for(i=1;i<n;i++)
53 scanf("%d",&num2[i]);
54 for(i=n-1;i>=0;i--)
55 {
56 Delete(0,num2[i]+1);
57 num1[i]=bj;
58 }
59 for(i=0;i<n;i++)
60 printf("%d\n",num1[i]);
61 }
62 return 0;
63}
64
65
66
2009年11月24日
题目连接：
滑雪
| Time Limit: 1000MS |
|
Memory Limit: 65536K |
| Total Submissions: 32414 |
|
Accepted: 11375 |
Description
Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。
Input
输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。
Output
输出最长区域的长度。
Sample Input
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
Sample Output
25
Source
我是用dp+记忆搜索，对对于每一个点，只搜一次。
基本思路是，对于每一个点（i，j），a[i][j].h表示此点的高度，a[i][j].x表示以此点为起点的最长距离，计算出以这个点为起点的最长距离，用dp（i，j）表示。然后找出最长的一个就为所要求的最长距离。对于任何一个点（i，j），只要找出与他相邻的且高度小于此点高度的一个最大的maxh，如果找不到与他相邻的且高度小于此点高度的点，maxh=0。显然可以求出a[i][j].h=maxh+1。
源程序：
#include<iostream>
#include<stdio.h>
using namespace std;
int m,n;
struct stu
{
int h,x;
}a[110][110];
int Max_x(int s1,int s2,int s3,int s4) //找出最大的
{
if(s2>s1)
s1=s2;
if(s3>s1)
s1=s3;
if(s4>s1)
s1=s4;
return s1;
}
void DP(int i,int j) //以（i，j）点为起点的最长距离
{
if(a[i][j].x)return ; //剪枝，当 （i，j）点已经算过了，就不用再算了否
//如果不剪枝程序会超时
int s1=0,s2=0,s3=0,s4=0;
if(i>0&&a[i][j].h>a[i-1][j].h)
{
DP(i-1,j);
s1=a[i-1][j].x;
}
if(j>0&&a[i][j].h>a[i][j-1].h)
{
DP(i,j-1);
s2=a[i][j-1].x;
}
if(i<n-1&&a[i][j].h>a[i+1][j].h)
{
DP(i+1,j);
s3=a[i+1][j].x;
}
if(j<m-1&&a[i][j].h>a[i][j+1].h)
{
DP(i,j+1);
s4=a[i][j+1].x;
}
a[i][j].x=1+Max_x(s1,s2,s3,s4);
}
int Skiing()
{
int i,j,s=0;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
if(!a[i][j].x) //如果此点已经算过，就不用再算了
DP(i,j);
if(a[i][j].x>s)
s=a[i][j].x;
}
return s; //返回最长的距离
}
int main()
{
int i,j,s;
while(cin>>n>>m)
{
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
scanf("%d",&a[i][j].h);
a[i][j].x=0;
}
s=Skiing();
printf("%d\n",s);
}
return 0;
}
|
2009年11月10日
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 76 Accepted Submission(s): 14
Problem Description
在非常流行的DOTA游戏中，补兵是非常重要的一种技术统计。如果一个单位被对方的多个单位攻击至死，则对该单位造成最后一次（致命的）伤害的攻击者将会获得更多的奖励（金钱和经验），这名攻击者被记录一次补兵。
现在假设有多个人攻击对方的一个单位，而你是其中的一个，你并不想在前面出手攻击，而只想打一次就直接将对方打死，完成一次补兵。假设其他人每次攻击的伤害和每两次攻击之间的间隔都是固定的，而你的攻击伤害也是固定的。输入将给出每个人两次攻击之间的间隔时间，并假设每个人第一次攻击的时刻值就是他的两次攻击之间的时间间隔值。例如，一个人攻击间隔为2，则他会在时刻2、4、6、8……进行攻击。
时间以整数计算。
如果多个人同时攻击导致对方死亡，攻击伤害最大的那个被记录一次补兵。如果你是攻击伤害最大的之一（还有其他和你攻击伤害一样的，但没有更大的），则你被记录一次补兵。
一个单位血量小于等于0就被判为死亡。
你的任务是求出合适的攻击时间段，使得这次补兵能够完成。这个时间段一定是一个区间，你需要输出的是它的两个端点。
Input
输入包含多组数据。每组数据第一行是一个整数N(2<=N<=1000)，表示攻击对方某个单位的人数。N=0表示输入结束。接下来有N-1行，每行两个整数，分别表示每个人每次攻击的伤害A(1<=A<=10)，以及每两次攻击之间的间隔T(1<=T<=100)。最后有一行包含两个整数，分别表示你的攻击伤害P(1<=P<=100000)以及对方单位的血量H(P<H<=1000000)。
Output
对每组数据，输出一行，如果不能完成补兵，输出’Impossible’，否则输出最早可以完成补兵的时间和最晚可以完成补兵的时间，用空格间隔。
Sample Input
Sample Output
8 10
Impossible
提示：
输入数据较多，尽量用scanf和printf代替cin和cout
代码：
#include<stdio.h>
int k;
struct stu
{
int x;
int mx;
}bu[110];
int f(int j)
{
int i,m=0,mxx=0;
for(i=1;i<=100;i++)
if(bu[i].mx)
m=m+(j/i)*bu[i].x;
return m;
}
int main()
{
int i,j,x,t,m,n,P,H,l,mxx;
double s,x1,t1,n1,y1;
while(scanf("%d",&n)&&n)
{
for(i=0;i<=100;i++)
bu[i].mx=bu[i].x=0;
s=0;
for(i=1;i<n;i++)
{
scanf("%d%d",&x,&t);
bu[t].x=bu[t].x+x;
if(x>bu[t].mx)bu[t].mx=x;
x1=x;
t1=t;
s=s+x1/t1;
}
scanf("%d%d",&P,&H);
x1=H;
y1=P;
n1=(x1-y1)/s;
n=n1;
if(n==0)n=1;
l=0;
for (i=n;i<=100+n;i++)
{ m=0;mxx=0;
for(j=1;j<=100;j++)
{
if(bu[j].mx)
{
m=m+(i/j)*bu[j].x;
if(i%j==0&&bu[j].mx>mxx)
mxx=bu[j].x;
}
}
if(m+P>=H&&mxx<=P){l=i;break;}
else if(m+P>=H)
break;
}
if(l==0)
{
printf("Impossible\n");
continue;
}
printf("%d",l);
n1=x1/s;
n=n1;
for(j=n+100;j>=l;j--)
{
m=0; mxx=0;
for(i=1;i<=100;i++)
{
if(bu[i].mx)
{
m=m+(j/i)*bu[i].x;
if(j%i==0&&bu[i].mx>mxx)
mxx=bu[i].mx;
}
}
if(m+P>=H&&mxx<=P&&f(j-1)<H){printf(" %d\n",j);break;}
}
}
return 0;
}
2009年11月8日
LC-Display
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 377 Accepted Submission(s): 143
Problem Description
A friend of you has just bought a new computer. Until now, the most powerful computer he ever used has been a pocket calculator. Now, looking at his new computer, he is a bit disappointed, because he liked the LC-display of his calculator so much. So you decide to write a program that displays numbers in an LC-display-like style on his computer.
Input
The input contains several lines, one for each number to be displayed. Each line contains two integers s, n (1 <= s <= 10, 0 <= n <= 99 999 999), where n is the number to be displayed and s is the size in which it shall be displayed.
The input file will be terminated by a line containing two zeros. This line should not be processed.
Output
Output the numbers given in the input file in an LC-display-style using s ``-'' signs for the horizontal segments and s ``|'' signs for the vertical ones. Each digit occupies exactly s+2 columns and 2s+3 rows. (Be sure to fill all the white space occupied by the digits with blanks, also for the last digit.) There has to be exactly one column of blanks between two digits.
Output a blank line after each number. (You will find a sample of each digit in the sample output.)
Sample Input
Sample Output
-- -- --
| | | | | |
| | | | | |
-- -- -- --
| | | | |
| | | | |
-- -- --
--- --- --- --- ---
| | | | | | | |
| | | | | | | |
| | | | | | | |
--- --- ---
| | | | | | | |
| | | | | | | |
| | | | | | | |
--- --- --- ---
Source
Mid-Central European Regional Contest 1999 代码：
#include<iostream>
#include<string.h>
using namespace std
;
int bj
;
void K
(int n
)
{
int i
;
for(i
=0;i
<=n
+1;i
++) cout
<<" ";
if(bj
)
{ cout
<<endl
;
}
}
void H
(int n
)
{
int i
; cout
<<" ";
for(i
=0;i
<n
;i
++) cout
<<"-"; cout
<<" ";
if(bj
) cout
<<endl
;
}
void LL
(int n
)
{
int i
; cout
<<"|";
for(i
=0;i
<n
;i
++) cout
<<" "; cout
<<"|";
if(bj
)cout
<<endl
;
}
void Lq
(int n
)
{
int i
; cout
<<"|";
for(i
=0;i
<=n
;i
++) cout
<<" ";
if(bj
) cout
<<endl
;
}
void Lh
(int n
)
{
int i
;
for(i
=0;i
<=n
;i
++) cout
<<" "; cout
<<"|";
if(bj
)cout
<<endl
;
}
void f
(int n
,int k
,int t
)
{
if(t
%2)
{
if(n
==1||n
==0&&t
==3||n
==4&&t
!=3||n
==7&&t
!=1) K
(k
);
else H
(k
);
}
else if(t
==2)
{
if(n
&&n
<4||n
==7) Lh
(k
);
else if(n
==5||n
==6) Lq
(k
);
else LL
(k
);
}
else
{
if(n
%2||n
==4) Lh
(k
);
else if(n
==2) Lq
(k
);
else LL
(k
);
}
}
int main()
{
char ch
[20];
int a
[20],i
,j
=0,k
,n
,m
,l
;
while(cin
>>n
>>ch
)
{ l
=strlen
(ch
);
for(i
=0;i
<l
;i
++) a
[i
]=ch
[i
]-'0';
if(n
==0&&l
==1&&a
[0]==0)break;
if(l
==1)bj
=1;
else bj
=0; f
(a
[0],n
,1);
for(i
=1;i
<l
;i
++)
{ bj
=0;
if(i
==l
-1) bj
=1; cout
<<" "; f
(a
[i
],n
,1);
}
for(k
=0;k
<n
;k
++)
{ bj
=0;
if(l
==1)bj
=1; f
(a
[0],n
,2);
for(i
=1;i
<l
;i
++)
{ bj
=0;
if(i
==l
-1) bj
=1; cout
<<" "; f
(a
[i
],n
,2);
}
} bj
=0;
if(l
==1)bj
=1; f
(a
[0],n
,3);
for(i
=1;i
<l
;i
++)
{ bj
=0;
if(i
==l
-1) bj
=1; cout
<<" "; f
(a
[i
],n
,3);
}
for(k
=0;k
<n
;k
++)
{ bj
=0;
if(l
==1)bj
=1; f
(a
[0],n
,4);
for(i
=1;i
<l
;i
++)
{ bj
=0;
if(i
==l
-1) bj
=1; cout
<<" "; f
(a
[i
],n
,4);
}
} bj
=0;
if(l
==1)bj
=1; f
(a
[0],n
,5);
for(i
=1;i
<l
;i
++)
{ bj
=0;
if(i
==l
-1) bj
=1; cout
<<" "; f
(a
[i
],n
,5);
} cout
<<endl
;
}
return 0;
}
2009年10月18日
Message Flood
Time Limit:2000MS Memory Limit:65536K
Total Submit:38 Accepted:8
Description
Well, how do you feel about mobile phone? Your answer would probably be something like that "It's so convenient and benefits people a lot". However, If you ask Merlin this question on the New Year's Eve, he will definitely answer "What a trouble! I have to keep my fingers moving on the phone the whole night, because I have so many greeting message to send!" Yes, Merlin has such a long name list of his friends, and he would like to send a greeting message to each of them. What's worse, Merlin has another long name list of senders that have sent message to him, and he doesn't want to send another message to bother them Merlin is so polite that he always replies each message he receives immediately). So, before he begins to send message, he needs to figure to how many friends are left to be sent. Please write a program to help him.
Here is something that you should note. First, Merlin's friend list is not ordered, and each name is alphabetic strings and case insensitive. These names are guaranteed to be not duplicated. Second, some senders may send more than one message to Merlin, therefore the sender list may be duplicated. Third, Merlin is known by so many people, that's why some message senders are even not included in his friend list.
Input
There are multiple test cases. In each case, at the first line there are two numbers n and m (1<=n,m<=20000), which is the number of friends and the number of messages he has received. And then there are n lines of alphabetic strings(the length of each will be less than 10), indicating the names of Merlin's friends, one per line. After that there are m lines of alphabetic strings, which are the names of message senders.
The input is terminated by n=0.
Output
For each case, print one integer in one line which indicates the number of left friends he must send.
Sample Input
5 3
Inkfish
Henry
Carp
Max
Jericho
Carp
Max
Carp
0
Sample Output
3
Source
ZSCPC9pre
代码：
#include<iostream>
#include<string.h>
using namespace std;
int s,len,sum; // len 字符串长度
char x[11]; //要记录或要查找的字符串
struct stu
{
int k; // 标记是否存在次字符串
int a[26];
}str[200000];
void ws() // 结点初始化函数
{
int i;
str[s].k=0;
for(i=0;i<26;i++)
str[s].a[i]=0;
}
void zds(int i,int j) // 建立字符串函数
{
if(j==len) //当第j等于字符串长度时说明第j-1个字符为最后一个字符
{
str[i].k=1; //标记k=1；
return ;
}
if(x[j]>='A'&&x[j]<='Z')
x[j]=x[j]+'a'-'A';
int m=x[j]-'a';
if(str[i].a[m]==0) //此字符的下一个字符不存在当前的字典数中，新建一个结点
{
ws();
str[i].a[m]=s;
s++;
}
zds(str[i].a[m],j+1); //建立下一个字符
}
void cz(int i,int j) //查找字符串函数
{
if(j==len) // 查找到最后一个字符时结束
{
if(str[i].k)
{
str[i].k=0; //如果此字符存在，k变为0（即在字典中删除此串）
sum++; // 如果此字符存在sum加一，
}
return ;
}
if(x[j]>='A'&&x[j]<='Z')
x[j]=x[j]+'a'-'A';
int m=x[j]-'a';
if(str[i].a[m]==0)return ; // 如果当前字符的下一个字符不存在，结束查找
cz(str[i].a[m],j+1);
}
int main()
{
int m,n,i;
while(cin>>n)
{
if(n==0)break;
cin>>m;
s=0;
ws();
s=1;
for(i=0;i<n;i++)
{
scanf("%s",x);
len=strlen(x);
zds(0,0);
}
sum=0;
for(i=0;i<m;i++)
{
scanf("%s",x);
len=strlen(x);
cz(0,0);
}
n=n-sum;
printf("%d\n",n);
}
return 0;
}
2009年10月9日
I Hate It
Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2952 Accepted Submission(s): 929
Problem Description
很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。
这让很多学生很反感。
不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。
Input
本题目包含多组测试，请处理到文件结束。
在每个测试的第一行，有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 )，分别代表学生的数目和操作的数目。
学生ID编号分别从1编到N。
第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。
接下来有M行。每一行有一个字符 C (只取'Q'或'U') ，和两个正整数A，B。
当C为'Q'的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。
当C为'U'的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。
Output
对于每一次询问操作，在一行里面输出最高成绩。
Sample Input
5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5
Sample Output
我的代码：
#include<iostream>
using namespace std;
int n;
int sum;
struct stu
{
int x,y,ms,z,k;
}st[2000010];
int maxm(int x,int y)
{
if(x>y)return x;
else return y;
}
void ws()
{
int m=n;
int i,j=1;
while(m/2)
{
for(i=1;i<=m/2;i++,j=j+2)
{
st[i+n].x=st[j].x;
st[i+n].y=st[j+1].y;
st[i+n].ms=maxm(st[j].ms,st[j+1].ms);
st[j].z=st[j+1].z=i+n;
st[j+1].k=j;
st[j].k=j+1;
st[i+n].z=st[i+n].k=0;
}
if(m%2)
{
st[i+n].x=st[j].x;
st[i+n].y=st[j].y;
st[i+n].ms=st[j].ms;
st[j].z=i+n;
st[j].k=j;
m++;
i++;
}
j=n+1;
m=m/2;
n=n+i-1;
}
}
void gs(int k)
{
int i=st[k].z;
int j=st[k].k;
if(i==0||maxm(st[k].ms,st[j].ms)==st[i].ms)
return ;
else
{
st[i].ms=maxm(st[k].ms,st[j].ms);
gs(i);
}
}
void out(int x,int y)
{
int i;
if(sum<st[x].ms)sum=st[x].ms;
i=x;
while(st[i].z&&y>=st[st[i].z].y&&x<=st[st[i].z].x)
{
i=st[i].z;
if(sum<st[i].ms)
sum=st[i].ms;
}
if(y==st[i].y)return;
else out(st[i].y+1,y);
return ;
}
int main()
{
int i,m,x,y;
char ch;
while(cin>>n>>m)
{
for(i=1;i<=n;i++)
{
scanf("%d",&st[i].ms);
st[i].x=st[i].y=i;
}
ws();
getchar();
for(i=0;i<m;i++)
{
scanf("%c%d%d",&ch,&x,&y);
getchar();
if(ch=='Q')
{
sum=0;
out(x,y);
printf("%d\n",sum);
}
else
{
st[x].ms=y;
gs(x);
}
}
}
return 0;
}
2009年8月19日
搬寝室
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2626 Accepted Submission(s): 807
Problem Description
搬寝室是很累的,xhd深有体会.时间追述2006年7月9号,那天xhd迫于无奈要从27号楼搬到3号楼,因为10号要封楼了.看着寝室里的n件物品,xhd开始发呆,因为n是一个小于2000的整数,实在是太多了,于是xhd决定随便搬2*k件过去就行了.但还是会很累,因为2*k也不小是一个不大于n的整数.幸运的是xhd根据多年的搬东西的经验发现每搬一次的疲劳度是和左右手的物品的重量差的平方成正比(这里补充一句,xhd每次搬两件东西,左手一件右手一件).例如xhd左手拿重量为3的物品,右手拿重量为6的物品,则他搬完这次的疲劳度为(6-3)^2 = 9.现在可怜的xhd希望知道搬完这2*k件物品后的最佳状态是怎样的(也就是最低的疲劳度),请告诉他吧.
Input
每组输入数据有两行,第一行有两个数n,k(2<=2*k<=n<2000).第二行有n个整数分别表示n件物品的重量(重量是一个小于2^15的正整数).
Output
对应每组输入数据,输出数据只有一个表示他的最少的疲劳度,每个一行.
Sample Input
Sample Output
#include<iostream>
#include<stdio.h>
#include<algorithm>
long a[1010][2010],b[2010];
using namespace std;
int main()
{
long i,j,k,n,m,sum;
while(scanf("%ld%ld",&n,&k)==2)
{
for(i=0;i<n;i++)
scanf("%ld",&b[i]);
sort(b,b+n);
for(i=1;i<n;i++)
a[0][i]=(b[i]-b[i-1])*(b[i]-b[i-1]);
a[1][1]=a[0][1];
for(i=2;i<n;i++)
if(a[1][i-1]<a[0][i])
a[1][i]=a[1][i-1];
else a[1][i]=a[0][i];
for(i=2;i<=k;i++)
{
a[i][2*i-1]=a[i-1][2*i-3]+a[0][2*i-1];
for(j=2*i;j<n;j++)
if(a[i][j-1]<a[i-1][j-2]+a[0][j])
a[i][j]=a[i][j-1];
else
a[i][j]=a[i-1][j-2]+a[0][j];
}
printf("%ld\n",a[k][n-1]);
}
return 0;
}
Prime Ring Problem
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3433 Accepted Submission(s): 1520
Problem Description
A ring is compose of n circles as shown in diagram. Put natural number 1, 2, ..., n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.
Note: the number of first circle should always be 1.
Input
n (0 < n < 20).
Output
The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographical order.
You are to write a program that completes above process.
Print a blank line after each case.
Sample Input
Sample Output
Case 1:
1 4 3 2 5 6
1 6 5 2 3 4
Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2
#include<iostream>
#include<stdio.h>
int g[50],a[30],b[30],n;
using namespace std;
void sous(int k,int m)
{
a[k]=m;
if(k==n)
{
if(g[1+m]==0)
return ;
printf("%d",a[1]);
for(int i=2;i<=n;i++)
printf(" %d",a[i]);
printf("\n");
return ;
}
for(int i=2;i<=n;i++)
if(b[i]&&g[i+m])
{
b[i]=0;
sous(k+1,i);
b[i]=1;
}
}
int main()
{
int i,j,k=1;
for(i=0;i<42;i++)
g[i]=0;
g[2]=g[3]=g[5]=g[7]=g[11]=g[13]=g[17]=g[19]=g[23]=g[29]=g[31]=g[37]=g[41]=1;
while(cin>>n)
{
for(i=0;i<=n;i++)
b[i]=1;
printf("Case %d:\n",k++);
sous(1,1);
printf("\n");
}
return 0;
}
Dream City
Time Limit: 1 Second Memory Limit: 32768 KB
JAVAMAN is visiting Dream City and he sees a yard of gold coin trees. There are n trees in the yard. Let's call them tree 1, tree 2 ...and tree n. At the first day, each tree i has ai coins on it (i=1, 2, 3...n). Surprisingly, each tree i can grow bi new coins each day if it is not cut down. From the first day, JAVAMAN can choose to cut down one tree each day to get all the coins on it. Since he can stay in the Dream City for at most m days, he can cut down at most m trees in all and if he decides not to cut one day, he cannot cut any trees later. (In other words, he can only cut down trees for consecutive m or less days from the first day!)
Given n, m, ai and bi (i=1, 2, 3...n), calculate the maximum number of gold coins JAVAMAN can get.
Input
There are multiple test cases. The first line of input contains an integer T (T <= 200) indicates the number of test cases. Then T test cases follow.
Each test case contains 3 lines: The first line of each test case contains 2 positive integers n and m (0 < m <= n <= 250) separated by a space. The second line of each test case contains n positive integers separated by a space, indicating ai. (0 < ai <= 100, i=1, 2, 3...n) The third line of each test case also contains n positive integers separated by a space, indicating bi. (0 < bi <= 100, i=1, 2, 3...n)
Output
For each test case, output the result in a single line.
Sample Input
2
2 1
10 10
1 1
2 2
8 10
2 3
Sample Output
10
21
Hints:
Test case 1: JAVAMAN just cut tree 1 to get 10 gold coins at the first day.
Test case 2: JAVAMAN cut tree 1 at the first day and tree 2 at the second day to get 8 + 10 + 3 = 21 gold coins in all.
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
struct P
{
int x,y;
}a[300];
bool cmp( P x,P y )
{
return x.y<y.y;
}
int f(int x,int y)
{
if(x>y)
return x;
return y;
}
int main()
{
int dp[300][300],i,j,m,n,t;
cin>>t;
while(t--)
{
cin>>n>>m;
for(i=1;i<=n;i++)
scanf("%d",&a[i].x);
for(i=1;i<=n;i++)
scanf("%d",&a[i].y);
sort(a+1,a+n+1,cmp);
dp[0][0]=0;
for(i=1;i<=m;i++)
{
dp[i][i]=dp[i-1][i-1]+a[i].x+a[i].y*(i-1);
for(j=i+1;j<=n;j++)
dp[i][j]=f(dp[i][j-1],dp[i-1][j-1]+a[j].x+a[j].y*(i-1));
}
printf("%d\n",dp[m][n]);
}
return 0;
}