Description

Input

Output

Sample Input

5
1
2
1
0

Sample Output

2
4
5
3
1

Source

 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

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

在非常流行的DOTA游戏中，补兵是非常重要的一种技术统计。如果一个单位被对方的多个单位攻击至死，则对该单位造成最后一次（致命的）伤害的攻击者将会获得更多的奖励（金钱和经验），这名攻击者被记录一次补兵。
现在假设有多个人攻击对方的一个单位，而你是其中的一个，你并不想在前面出手攻击，而只想打一次就直接将对方打死，完成一次补兵。假设其他人每次攻击的伤害和每两次攻击之间的间隔都是固定的，而你的攻击伤害也是固定的。输入将给出每个人两次攻击之间的间隔时间，并假设每个人第一次攻击的时刻值就是他的两次攻击之间的时间间隔值。例如，一个人攻击间隔为2，则他会在时刻2、4、6、8……进行攻击。
时间以整数计算。
如果多个人同时攻击导致对方死亡，攻击伤害最大的那个被记录一次补兵。如果你是攻击伤害最大的之一（还有其他和你攻击伤害一样的，但没有更大的），则你被记录一次补兵。
一个单位血量小于等于0就被判为死亡。
你的任务是求出合适的攻击时间段，使得这次补兵能够完成。这个时间段一定是一个区间，你需要输出的是它的两个端点。

2
2 2
3
10
2
20 2
3
10
0

8 10
Impossible
提示：
输入数据较多，尽量用scanf和printf代替cin和cout

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 377    Accepted Submission(s): 143

2 12345
3 67890
0 0

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

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 a_i coins on it (i=1, 2, 3...n). Surprisingly, each tree i can grow b_i 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, a_i and b_i (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 a_i. (0 < a_i <= 100, i=1, 2, 3...n) The third line of each test case also contains n positive integers separated by a space, indicating b_i. (0 < b_i <= 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;
}