2011年3月24日

## stl

posted @ 2011-03-24 12:17 陈烈 阅读(234) | 评论 (0)编辑 收藏

2009年11月27日

## poj（北大 2182) Lost Cows

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

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

posted @ 2009-11-27 20:13 陈烈 阅读(450) | 评论 (0)编辑 收藏

2009年11月24日

## puk 1088 滑雪

 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```

Input

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;
}

posted @ 2009-11-24 17:32 陈烈 阅读(380) | 评论 (0)编辑 收藏

2009年11月10日

# 题目来源：http://acm.hdu.edu.cn/showproblem.php?pid=2542补兵

Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 76    Accepted Submission(s): 14

Problem Description

Input

Output

Sample Input
```2
2 2
3
10
2
20 2
3
10
0```

Sample Output
```8 10
Impossible

#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;
}

posted @ 2009-11-10 11:54 陈烈 阅读(662) | 评论 (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
```2 12345
3 67890
0 0```

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;
}

posted @ 2009-11-08 19:38 陈烈 阅读(426) | 评论 (1)编辑 收藏

2009年10月18日

## Message Flood（字典树）

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;
}

posted @ 2009-10-18 13:17 陈烈 阅读(525) | 评论 (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

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
```5
6
5
9
```

#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;
}

posted @ 2009-10-09 19:52 陈烈 阅读(1106) | 评论 (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

Input

Output

Sample Input
```2 1
1 3```

Sample Output
`4`
#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;
}

posted @ 2009-08-19 19:16 陈烈 阅读(447) | 评论 (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
```6
8```

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;
}

posted @ 2009-08-19 19:09 陈烈 阅读(709) | 评论 (0)编辑 收藏

## 浙大 3211

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;
}

posted @ 2009-08-19 19:04 陈烈 阅读(239) | 评论 (0)编辑 收藏

 < 2024年4月 >
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

• 随笔 - 10
• 文章 - 0
• 评论 - 1
• 引用 - 0

•